Совсем детский вопрос или "Задача о сдаче"

KeSqueer
Ага, и скорость полного перебора будет O(2^n). Не пойдет.

 

динамическое программирование подойдет только если нужная сумма ограничена сверху вменяемым числом (1кк вполне нормально).
ну и нет там никаких собственно трудностей.
для i+1 элемента пробуем пробегаться k=0..i и находим минимальное значение coins[k] + coins[i - k]
сложность - n^2, где n - значение сдачи.

 

n0name,Enchantner

Сумма "сдачи" может быть любой, т.к. данную сумму можно свести к значению S < 2*B(n)
(где B(n) - самая большая "монета" или другими словами максимальный элемент базиса
{B(n) B(n-1) ...B(1)}) просто вычитая из заданного значение сдачи значение, кратное B(n).
Надеюсь, с этим вы спорить не будете...

После этого нужно выполнить всего n итераций 'жадного' алгоритма (#8) для всех базисов:

{B(n) B(n-1) ...B(1)}
{B(n-1) B(n-2) ...B(1)}
...
{B(2) B(1)}
{B(1)}

и выбрать то решение, где количество монет будет наименьшим.

Например, для примера 425 - {1,125,300,400}
Решение будет таковым:
{1,125,300,400} - 400*1+1*25 = 26м
{1,125,300} - 300*1+125*1 = 2м
{1,125} - 125*3 + 1*50 = 53м
{1} - 1*425 = 425v

Мин число монет - 2 (300+125)

Для числа 825 - сначала 825-400=425 (<2*400) - далее - вышеприведенные расчеты.