【ダイナミックプランニング】コインお釣り
， ， ， ，
， ， 。
， 100，50，20，10，5，2，1，0.5，0.2，0.1，0.05，
0.02，0.01 ， 。
： ， ，
。 ， 40，30，25 ， 37
；95 3。 ， 10，7，5，1
， 12 3， 2。
： ， ；
， ， 。
：
1 ， N T， 1≤N≤50 ；1≤T≤100000
。
2 N 65535 ， 。
：
T ， 。
T ， 。
：coin.in
4 12
10 7 5 1
：coin.out
2 簡単な完全なリュックサックで、多く言う必要はありません.O(mn)のアルゴリズムは,プログラムに示すように,ゼロ壹リュックのその場スクロールの副作用(すなわち,変逆列挙空間が正の列挙)を利用する.ACCode:
#include <cstdio>
int f[100010], c[60], n, m;
int min(int a, int b) {return a < b ? a : b; }
int main()
{
freopen("coin.in", "r", stdin);
freopen("coin.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i < n + 1; ++i)
scanf("%d", c + i);
for (int j = 1; j < m + 1; ++j)
f[j] = 0x3fffff00;
for (int i = 1; i < n + 1; ++i)
for (int j = c[i]; j < m + 1; ++j)
f[j] = min(f[j], f[j - c[i]] + 1);
for (int j = m; j > 0; --j)
if (f[j] < 0x3fffff00)
{printf("%d", f[j]); break; }
return 0;
}