UVa 147 Dollars（完全背包）

题意：

换零钱，计算方案数。

思路：

完全背包，UVa674的加强版。

 1 #include<iostream> 
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 30000 + 5;
 8 int coin[] = { 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
 9 long long d[maxn];
10 
11 int main()
12 {
13     //freopen("D:\txt.txt", "r", stdin);
14     int i, j;
15     memset(d, 0, sizeof(d));
16     d[0] = 1;
17     for (int i = 0; i < 11;i++)
18     for (int j = coin[i]; j <= maxn; j++)
19         d[j] += d[j - coin[i]];
20     double s;
21     while (cin >> s && s)
22     {
23         int n = (int)(100 * s + 0.5);
24         printf("%6.2lf%17lld
", s,d[n]);
25     }
26     return 0;
27 }