Cash Machine(多重背包)

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=1000020;
 4 #define Max(a,b) (a)>(b)?(a):(b)
 5 int dp[N],cash;
 6 void ZeroOnePack(int cost)//01背包
 7 {
 8     for (int i = cash; i >= cost; i--)
 9     {
10         dp[i] = Max(dp[i],dp[i-cost]+cost);
11     }
12 }
13 void ComplexPack(int cost)//完全背包
14 {
15     for (int i = cost; i <= cash; i++)
16     {
17         dp[i] = Max(dp[i],dp[i-cost]+cost);
18     }
19 }
20 void MultiplePack(int cnt,int cost)//多重背包
21 {
22     if (cnt*cost > cash)
23         ComplexPack(cost);
24     else
25     {
26         int k = 1;
27         while(k < cnt)
28         {
29             ZeroOnePack(k*cost);
30             cnt-=k;
31             k<<=1;
32         }
33         ZeroOnePack(cnt*cost);
34     }
35 }
36 int main()
37 {
38     int n,cost[12],cnt[12];
39     while(~scanf("%d %d",&cash,&n))
40     {
41         for (int i = 1; i <= n; i++)
42         {
43             scanf("%d %d",&cnt[i],&cost[i]);
44         }
45         memset(dp,0,sizeof(dp));
46         for (int i = 1; i <= n; i++)
47         {
48             MultiplePack(cnt[i],cost[i]);
49         }
50         printf("%d\n",dp[cash]);
51     }
52     return 0;
53 }