0
ответов
Построение дробей Задача на собеседовании
Недавно я наткнулся на следующий вопрос на собеседовании. Мне было интересно, сработает ли подход динамического программирования и/или есть ли какое-то математическое понимание, которое сделало бы...
вопрос задан: 7 May 2012 08:52
0
ответов
Максимизируйте сумму «не -перекрывающихся» чисел из матрицы
Просто ищу немного направления, я понимаю, что приведенный пример можно решить, используя итерацию грубой силы, но я ищу более элегантный (т.е. математический? )решение, которое могло бы...
вопрос задан: 30 April 2012 19:02
0
ответов
Обобщенная головоломка с двумя-яйцами
Вот описание проблемы :Предположим, что мы хотим знать, с каких этажей в N-этажном здании безопасно сбрасывать яйца, а какие вызовут ломаться при посадке. Мы делаем несколько...
вопрос задан: 16 April 2012 19:34
0
ответов
Алгоритм Кадана в Java
У меня есть следующая реализация алгоритма Кадана в Java. Это в основном, чтобы найти максимальную сумму непрерывной подложки. Строка [] номера = string.split (","); int max_so_far ...
вопрос задан: 12 April 2012 04:34
0
ответов
Упражнение по динамическому программированию для разрезания строки
Я работал над следующей задачей из этой книги. Определенный язык обработки строк-предлагает примитивную операцию, которая разбивает строку на две части. Поскольку эта операция требует...
вопрос задан: 9 April 2012 05:49
0
ответов
Динамический алгоритм автокоррекции текста
Я пишу программу автокоррекции, которая использует расстояние Левенштейна для исправления фразы длиной не более 64 символов на основе определенного словаря, содержащего 8000 слов. Словарь...
вопрос задан: 7 April 2012 08:08
0
ответов
Квадратная подпоследовательность
Строка называется квадратной строкой, если ее можно получить путем объединения двух копий одной и той же строки. Например, «абаб», «аа» — это квадратные строки, а «ааа», «абба» — нет. Учитывая строку, как...
вопрос задан: 4 April 2012 15:41
0
ответов
Поиск кратчайших комбинаций в массиве/последовательности, равной сумме
Я совсем запутался и понятия не имею, как решить эту проблему. Допустим, у меня есть массив arr = [1, 4, 5, 10] и число n = 8. Мне нужна кратчайшая последовательность внутри arr, равная n. Итак, для...
вопрос задан: 1 April 2012 17:28
0
ответов
Проблемы с динамическим программированием
У меня трудности с пониманием динамического программирования , поэтому я решил решить некоторые проблемы. Я знаю основные динамические алгоритмы, такие как самая длинная общая подпоследовательность, задача о рюкзаке, но я знаю их...
вопрос задан: 25 March 2012 17:48
0
ответов
Максимальная сумма прямоугольного подмассива
Учитывая массив действительных чисел, A[1..n,1..n], я хочу найти подмассив B = A[i ..j,s..t] с 1 <= i <= j <= n и 1 <= s <= t <= n такими, что сумма чисел в ...
вопрос задан: 21 March 2012 08:14
0
ответов
Динамическое программирование: Алгоритм решения следующей задачи?
Недавно я выполнил следующее упражнение на собеседовании: «Робота можно запрограммировать на пробежку «а», «б», «в»… «n» километров, и это займет ta, tb, tc… tn. минут соответственно. Как только он добежит до...
вопрос задан: 13 March 2012 18:17
0
ответов
Рюкзак 0-1 с ограничениями разделения
У меня проблема, которая на первый взгляд выглядит как рюкзак 0-1. У меня есть набор возможных «кандидатов», которых можно выбрать (или нет), у каждого кандидата есть «вес» (стоимость) и потенциальная «ценность». Были ...
вопрос задан: 4 February 2012 19:37
0
ответов
Динамическое программирование и разделяй и властвуй
Я читал заметки по динамическому программированию и натолкнулся на следующий комментарий. Если подзадачи не являются независимыми, то есть подзадачи поделитесь подзадачами, затем разделите и победите ...
вопрос задан: 24 January 2012 04:21
0
ответов
Рюкзак с непрерывным (неотличимым) ограничением
Я смотрел «Динамическое программирование - задача Капсака» (YouTube). Однако я решаю немного другую задачу, где ограничением является бюджет, цена в двойном, а не в целочисленном формате. Так что мне интересно, как ...
вопрос задан: 21 January 2012 15:24
0
ответов
Решение оптимизации (Найдите минимальное количество времени, необходимое для того, чтобы каждый поднялся и спустился с горы)
Задача выглядит следующим образом (переведено): Есть n (n <= 25000) человек у подножия горы, и каждый хочет сначала подняться, а потом спуститься с горы. Есть 2 гида: один для ...
вопрос задан: 10 January 2012 21:04
0
ответов
Data.MemoCombinators, где я могу найти примеры?
В этом пакете есть несколько функций для преобразования рекурсивных функций в рекурсивные функции динамического программирования для повышения производительности: http://hackage.haskell.org/packages/archive/data-memocombinators/0.3 / ...
вопрос задан: 18 November 2011 07:20
0
ответов
0-1 Алгоритм рюкзака
Разрешима ли следующая задача рюкзака 0-1: положительные значения 'float' и веса 'float' (могут быть положительными или отрицательными) {{ 1}} 'float' вместимость ранца> 0 У меня в среднем <10 предметов, поэтому я '...
вопрос задан: 14 November 2011 17:14
0
ответов
Вариант резки стержня
Вам дается деревянная палка длиной X с метками m на ней на произвольные места (интегральные), а маркировка подсказывает, где должны быть сделаны соответствующие разрезы. Для того, чтобы разрезать палку длиной L
на ...
вопрос задан: 13 November 2011 21:29
0
ответов
Алгоритм O (n ^ 2) (или O (n ^ 2lg (n))?) Для вычисления Самая длинная общая подпоследовательность (LCS) из двух «кольцевых» строк
Это проблема, появившаяся на сегодняшнем олимпиаде по программированию в Северо-западном регионе Тихого океана, в ходе которой ее никто не решил. Это проблема B, и полный набор задач находится здесь: http://www.acmicpc-pacnw.org/icpc -...
вопрос задан: 6 November 2011 06:03
0
ответов
Алгоритм заключения выражения в скобки, чтобы максимизировать его значение
Я обнаружил это, когда искал задачи по динамическому программированию.
Вам дано выражение без скобок в форме V0 O0 V1 O1 .... Vn-1 Мы должны поставить скобки в местах, которые максимизируют ...
вопрос задан: 5 November 2011 17:35
0
ответов
Интервью на Facebook: узнайте порядок, в котором дается максимальная сумма, выбрав поля с номером в кольце, когда два рядом с ним будут уничтожены
Не нашел подобного вопроса по этому поводу. Это последний вопрос на Facebook: вы получили кольцо с ящиками. Каждая коробка имеет неотрицательное число на нем, может быть дубликатом. Написать функцию / ...
вопрос задан: 28 October 2011 22:58
0
ответов
Нахождение оптимального решения, которое минимизирует ограничение?
Назовем эту проблему проблемой Slinger-Bird (на самом деле Slinger аналогичен серверу, а птица - запросу, но у меня был нервный срыв, думая об этом поэтому я изменил их ...
вопрос задан: 28 October 2011 09:59
0
ответов
Максимальная сумма непрерывной последовательности длиной не менее L
Итак, для следующего массива, где L = 3 -5 -1 2 -3 0 -3 3 Наилучшей возможной суммой длиной не менее 3 будет 0, где последовательность - это три последних элемента (0, -3, 3) Как вы можете вычислить ...
вопрос задан: 26 October 2011 20:51
0
ответов
Можно ли на Лиспе выполнять восходящее динамическое программирование?
Может ли типичный диалект Лиспа решать проблемы, используя восходящий подход «динамического программирования» ? (Обратите внимание: я не говорю о «мемоизации», которая, насколько я понимаю, тривиальна с использованием любого ...
вопрос задан: 19 October 2011 16:56
0
ответов
Наибольшая прямоугольная подматрица с тем же номером
Я пытаюсь придумать алгоритм динамического программирования, который находит наибольшую подматрицу в матрице, состоящей из того же числа: пример: {5 5 8}
{5 5 7}
{3 4 1} Ответ: 4 элемента ...
вопрос задан: 14 October 2011 22:15
0
ответов
Распределение шаров по «ящикам с заданной емкостью» с помощью динамического программирования
Мне было интересно, как решить такую проблему с помощью DP. Учитывая n шаров и m ящиков, каждая ячейка имеет макс. вместимость c1, c2, ... см. Каково общее количество способов распределить эти n шаров на эти m ...
вопрос задан: 5 October 2011 14:05
0
ответов
алгоритм динамического программирования во время интервью [закрыто]
Этот вопрос был задан мне во время интервью, и в нем были выявлены мои недостатки в динамическом программировании. Буду признателен, если кто-нибудь поможет мне взломать этот. Кроме того, было бы очень ...
вопрос задан: 3 October 2011 05:37
0
ответов
Динамическое программирование в системе Mathematica: как автоматически локализовать и / или очистить определения замеченных функций
В системе Mathematica 8.0, предположим, что у меня есть несколько констант: a:=7
b:=9
c:=13
d:=.002
e:=2
f:=1 и я хочу использовать их для оценки некоторых взаимосвязанных функций g[0,k_]:=0.
g[t_,0]:=e
g[t_,k_]:=g[t-1,k]*a+h[t-1,k-...
вопрос задан: 8 September 2011 16:11
0
ответов
Объясните алгоритм для решения «самой длинной растущей подпоследовательности»
. Я пытался понять этот алгоритм в течение последних двух часов, но не могу его получить. Может кто-нибудь, пожалуйста, объясните это легко понять? Функция lis_length (a) n: = a.length ...
вопрос задан: 2 September 2011 14:05
0
ответов
Организация строк в массиве для устранения растущих подпоследовательностей
Следующая проблема взята из проблем по алгоритмам (задача 653): вам дана матрица номеров N x 2. Найдите алгоритм o (n log n), который переписывает строки в массиве такой, что это ...
вопрос задан: 31 August 2011 10:27