poj1787_完全背包（个数不是无限个）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <vector>
10 using namespace std;
11 
12 int max(int a, int b)
13 {
14     return a > b ? a : b;
15 }
16 int dp[10010], num[5][10010], used[10010];
17 int main()
18 {
19     int a[5], p, c[5], i, j;
20     a[1] = 1, a[2] = 5, a[3] = 10, a[4] = 25;
21     while(~scanf("%d %d %d %d %d", &p, &c[1], &c[2], &c[3], &c[4]))
22     {
23         if(p + c[1] + c[2] + c[3] + c[4] == 0)
24             break;
25         memset(dp, -1, sizeof(dp));
26         memset(num, 0, sizeof(num));        
27         dp[0] = 0;
28         for(i = 1; i <= 4; i++)
29         {
30             memset(used, 0, sizeof(used));
31             for(j = a[i]; j <= p; j++)
32             {
33                 if(dp[j - a[i]] != -1 && used[j - a[i]] + 1 <= c[i] && dp[j] < dp[j - a[i]] + 1)
34                 {            
35                     dp[j] = dp[j - a[i]] + 1;      //组成p用的硬币总数              
36                     used[j] = used[j - a[i]] + 1;//组成P用的a[i]面值硬币的个数
37                     num[i][j] = used[j];
38                 }
39             }
40         }
41        // cout << used[p] ;
42         if(dp[p] == -1)
43             printf("Charlie cannot buy coffee.
");
44         else
45         {
46             int t4 = used[p];
47             int t3 = num[3][p - t4 * 25];
48             int t2 = num[2][p - t4 * 25 - t3 * 10];
49             int t1 = num[1][p - t4 * 25 - t3 * 10 - t2 * 5]; 
50             printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
", t1, t2, t3, t4);
51         }
52     }
53     return 0;
54 }