всех решений для изменения решений с динамическим программированием

я просматривал мои подачки для нашего класса алгоритма, и я начал думать об этом вопросе:всех решений для изменения решений с динамическим программированием

Учитывая различные типы монет с различными значениями, найти все конфигурации монеты сложить до определенной суммы без дублирования.

Во время класса мы решили проблему, чтобы найти количество возможных путей для суммы и наименьшего количества монет для суммы. Однако мы никогда не пытались найти решения.

Я думал о решении этой проблемы при динамическом программировании.

Я пришел с версией рекурсии (для простоты я только напечатать решения):

void solve(vector<string>& result, string& currSoln, int index, int target, vector<int>& coins) 
{ 
    if(target < 0) 
    { 
     return; 
    } 

    if(target == 0) 
    { 
     result.push_back(currSoln); 
    } 

    for(int i = index; i < coins.size(); ++i) 
    { 
     stringstream ss; 
     ss << coins[i]; 
     string newCurrSoln = currSoln + ss.str() + " "; 
     solve(result, newCurrSoln, i, target - coins[i], coins); 
    } 
}

Однако я застрял при попытке использовать DP, чтобы решить эту проблему. У меня есть 2 основных препятствия:

Я не знаю, что структура данных следует использовать для хранения предыдущих ответов
Я не знаю, что моя снизу вверх процедура (с использованием циклов замены рекурсии) следует выглядит как.

Любая помощь приветствуется, и некоторые коды будут оценены!

Спасибо за ваше время.

источник

2014-08-27 Tianyu Lang

Для меня это не сразу становится очевидным, если вы можете использовать динамическое программирование для этой проблемы. Если я нахожу 50 центов, добавьте одну четверть и «рекурсию» на 25 центов, которая найдет 1 квартал и 5 ников. Затем я вернусь к началу, попробуйте 5 ников и проверьте результаты 25 центов, которые находят рассчитанные 2 решения, поэтому я говорю, что есть 4 общих решения. Но 1 квартал + 5 ников и 5 ников + 1 квартал - это дубликаты. –

Может быть экспоненциально много возможных решений для изменения, поэтому DP поможет, но может по-прежнему выполнять действительно, очень долгое время. Ты в порядке с этим? – templatetypedef

Я написал наивную версию для сравнения: http://coliru.stacked-crooked.com/a/d2c06ff6aa2ea45a –

В решении dp вы создаете набор промежуточных состояний и сколько способов туда добраться. Тогда ваш ответ - это число, которое попало в состояние успеха.

Итак, для подсчета изменений состояния - это то, что вы получили определенное количество изменений. Подсчет - это количество способов внесения изменений. И состояние успеха заключается в том, что вы сделали правильное изменение.

Чтобы перейти от подсчета решений к их перечислению, вам необходимо сохранить эти промежуточные состояния, а также сохранить запись в каждом состоянии всех состояний, которые перешли на этот, и информацию о том, как это сделать. (В случае подсчета изменений, то, как бы который монетой вы добавили.)

Теперь с этой информацией вы можете начать с состояния успеха и рекурсивно идти назад через структуры дп данных на самом деле найти решения, а чем счет. Хорошей новостью является то, что вся ваша рекурсивная работа эффективна - вы всегда смотрите только на пути, которые преуспевают, поэтому не тратьте время на то, что не будет работать. Но если есть миллиард решений, тогда нет королевского ярлыка, который позволяет быстро распечатать миллиард решений.

Если вы хотите быть немного умным, вы можете превратить это в полезное перечисление. Например, вы можете сказать: «Я знаю, что есть 4323431 решения, что такое 432134»? И найти это решение будет быстро.

источник

2014-08-27 19:52:51 btilly

так что вы имеете в виду в основном , В дополнение к двумерному массиву dp [i] [j], где i - оставшееся количество, а j - тип монеты, мне все еще нужно иметь другую структуру данных для хранения какой монеты я взял, когда перехожу из одного состояния в другое. Таким образом, когда я заканчиваю подсчет количества возможных способов, я могу использовать грубую силу, начиная с состояния финиша и пытаться найти все решения рекурсивно. Это в основном то, что вы говорите? –

@TianyuLang Звучит так, будто вы его получили. Это будет сделано, чтобы добавить связанный список, из которого другие государства вы пришли в состояние от, и добавлять к нему каждый раз, когда вы приходите в состояние. – btilly

Сразу видно, что вы можете использовать подход с динамическим программированием. Что не очевидно, что в большинстве случаев (в зависимости от номиналов монет) вы можете использовать жадный алгоритм, который, вероятно, будет более эффективным. См. Cormen, Leiserson, Rivest, Stein: Введение в алгоритмы 2-е изд., Проблемы 16.1.

источник

2014-08-27 19:54:55 user1666959

да. использование жадных было бы более эффективным, но это не общее решение. Поскольку это не сработает, если у вас есть тип монет, –

всех решений для изменения решений с динамическим программированием

ответ

Смежные вопросы