Все решения по внесению изменений с помощью динамического программирования ⇐ C++

[Anonymous]

Я просматривал раздаточные материалы для нашего класса по алгоритмам и начал думать над этим вопросом:

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

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

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

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

Код: Выделить всё

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

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

for(int i = index; i < coins.size(); ++i)
{
stringstream ss;
ss 

Подробнее здесь: [url]https://stackoverflow.com/questions/25534431/all-solutions-to-change-making-with-dynamic-programming[/url]