Точное изменение UVA

Question

Точное изменение UVA

Я решал следующую проблему.

и его алгоритм решения находится на http://www.algorithmist.com/index.php/UVa_11517

Псевдоалгоритм:

int dp[30001];

dp[0] = 0;
for (int i=1; i<=30000; i++)
dp[i] = INFINITE;

for each coin C do
for (int v = 30001 - C - 1; v >= 0; v--)
if (dp[v] < INFINITE)
dp[v+C] = min(dp[v+C], dp[v]+1);

Но я думаю, что его решение неверно.
Возьмем случай, когда номинал монеты:

Coins = [500,1000,1500]

и для price = 3000, Согласно вышеупомянутому решению, его ответ будет 3000 with 3 coins, Но 3000 можно получить из 2 монет 1500,
Пожалуйста, дайте мне знать, является ли это решение неправильным или правильным.

2

algorithm c++dynamic-programming onlinejudge

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Предлагаемое решение является правильным, поскольку у вас нет неограниченного количества монет каждого достоинства:

[I] Часто полезно приносить деньги.

Каждая из следующих n строк содержит одно целое число, значение в центах каждой купюры или монеты, которые у вас есть.

Именно поэтому цикл в предлагаемом решении уменьшается:

for (int v = 30001 - C - 1; v >= 0; v--)

Это позволяет избежать использования одной и той же монеты дважды, потому что когда она смотрит на dp[v] строить dp[v+C], dp[v] был построен без использования текущей монеты C.

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

for (int v = 0; v <= 30001 - C - 1; v++)

1