Алгоритм динамического программирования N, K проблема
Алгоритм, который возьмет два положительных числа N и K и вычислит самое большое количество, которое мы можем получить путем преобразования N в другое число через удаление K цифры от N.
Поскольку исключая, позвольте, говорят, что у нас есть N=12345 и K=3 так самое большое количество, которое мы можем получить путем удаления 3 цифр из N, 45 (другие преобразования были бы 12, 15, 35, но 45 является самым большим). Также Вы не можете изменить порядок цифр в N (таким образом, 54 не решение). Другим примером был бы N=66621542 и K=3, таким образом, решение будет 66654.
Я знаю, что это - связанная с динамическим программированием проблема, и я не могу получить идею о решении ее. Я должен решить это в течение 2 дней, таким образом, любая справка ценится. Если Вы не хотите решать это для меня, Вы не имеете к, но укажите на меня на прием или по крайней мере некоторые материалы, где я могу читать больше о некоторых подобных проблемах.
Заранее спасибо.
5 ответов
Уловка для решения задачи динамического программирования обычно заключается в выяснении того, как выглядит структура решения, и, более конкретно, показывает ли оно оптимальное подконструкция .
В этом случае мне кажется, что оптимальное решение с N = 12345 и K = 3 будет иметь оптимальное решение для N = 12345 и K = 2 как часть решения. Если вы можете убедить себя в том, что это верно, то вы сможете рекурсивно выразить решение проблемы. Затем либо реализуйте это с помощью запоминания, либо снизу вверх.
Двумя наиболее важными элементами любого решения динамического программирования являются:
- Определение правильных подзадач
- Определение рекуррентного отношения между ответом на подзадачу и ответ на более мелкие подзадачи
- Нахождение базовых случаев , наименьших подзадач, ответ на которые не зависит от других ответов
- Определение порядка сканирования , в котором вы должны решать подзадачи (чтобы вы никогда не использовали рекуррентное отношение, основанное на неинициализированных данных )
Вы узнаете, что у вас есть правильные подзадачи, когда
- Проблема, на которую вам нужен ответ to является одним из них
- Базовые случаи действительно тривиальны
- Повторяемость легко оценить
- Порядок сканирования прост
В вашем случае просто указать подпрограмму пятна. Поскольку это, вероятно, домашнее задание, я просто дам вам подсказку, что вы могли бы пожелать, чтобы в N было меньше цифр, чтобы начинаться с .
Это можно решить за O(L), где L = количество цифр. Зачем использовать сложные формулы DP, если можно воспользоваться стеком:
Для: 66621542 Добавьте цифру в стек, пока в стеке меньше или равно L - K цифр: 66621. Теперь удалите цифры из стека, пока они меньше, чем текущая считанная цифра, и поместите текущую цифру в стек:
прочитайте 5: 5 > 2, выведите 1 из стека. 5 > 2, также забираем 2. положить 5: 6665 читать 4: стек не заполнен, положить 4: 66654 читать 2: 2 < 4, ничего не делать.
Необходимо еще одно условие: не вынимайте из стека больше элементов, чем осталось цифр в вашем числе, иначе ваше решение будет неполным!
Другой пример: 12345 L = 5, K = 3 положите L - K = 2 цифры в стек: 12
прочитайте 3, 3 > 2, положите 2, 3 > 1, положите 1, положите 3. стек: 3 прочитать 4, 4 > 3, вывести 3, положить 4: 4 читаем 5: 5 > 4, но мы не можем положить 4, иначе у нас не останется достаточно цифр. поэтому кладем 5: 45.
Что ж, чтобы решить любую проблему динамического программирования, вам нужно разбить ее на повторяющиеся подрешения.
Допустим, мы определяем вашу проблему как A (n, k), которая возвращает наибольшее возможное число, удаляя k цифр из n.
Отсюда мы можем определить простой рекурсивный алгоритм.
Используя ваш пример, A (12345, 3) = max {A (2345, 2), A (1345, 2), A (1245, 2), A (1234, 2)}
В более общем смысле, A (n, k) = max {A (n с удаленной 1 цифрой, k - 1)}
И ваш базовый случай - A (n, 0) = n.
Используя этот подход, вы можете создать таблицу, в которой кэшируются значения n и k.
int A(int n, int k)
{
typedef std::pair<int, int> input;
static std::map<input, int> cache;
if (k == 0) return n;
input i(n, k);
if (cache.find(i) != cache.end())
return cache[i];
cache[i] = /* ... as above ... */
return cache[i];
}
Это простое решение, но есть лучшее решение, которое работает с очень маленьким одномерным кешем. Попробуйте перефразировать вопрос следующим образом: «Дана строка n и целое число k, найти лексикографически наибольшую подпоследовательность в n длины k». По сути, в этом и заключается ваша проблема, и решение гораздо проще.
Теперь мы можем определить другую функцию B (i, j) , которая дает наибольшую лексикографическую последовательность длины (i - j) , используя только первую i цифр n (другими словами, удалив j цифр из первых i цифр n ).
Используя ваш пример еще раз, у нас будет:
B (1, 0) = 1
B (2, 0) = 12
B (3, 0) = 123
B ( 3, 1) = 23
B (3, 2) = 3
и т. Д.
Немного подумав, мы можем найти рекуррентное соотношение:
B (i, j) = max (10B (i-1, j) + n i , B (i -1, j-1))
или, если j = i , то B (i, j) = B (i-1, j-1)
и B (0, 0) = 0
И вы можете закодировать это очень похоже на приведенное выше.
Вот что я думаю:
Рассмотрим первые k + 1 цифр слева. Найдите самый большой, найдите его и удалите цифры слева. Если существует два одинаковых наибольших числа, найдите крайнее левое и удалите числа слева от него. сохранить количество удаленных цифр (назовите его j).
Сделайте то же самое с новым числом как N и k + 1-j, как K. Делайте это, пока k + 1 -j не станет равным 1 (надеюсь, так и будет, если я не ошибаюсь).
Число, которое у вас получится, будет тем числом, которое вы ищете.