79ms Cash Machine
多重背包問題：
思想：
把多重背包問題轉化成01背包，假設某件物品的數量上限是n,每件的體積是c，價值是w
那么可把該物品分成系數是1,2,4……，2^(k-1), 和n-2^k+1,（k的滿足2^k<n）的最大整數
那么新的物品就是（體積，價值）（1*c，1*w），（2*c，2*w），（4*c，4*w），
……（2^k*c，2^k*w），（（n-2^k+1）*c，(n-2^k+1)*w）
例如7可以分成系數為1,2，4。 13得到系數為1,2,4,6的物品。
這樣構造出來的物品和原來數量小于等于n的情況等同，即原來該物品可取的任意數量，可以由這些物品組合得到。
如比如7那個例子，取6個物品，可由2,4得到。取3個物品可由，1,2得到。
deal()就是完成這樣的任務。
1
2 #include<iostream>
3 #include<algorithm>
4 #include<string.h>
5 using namespace std;
6 int c[10001]={0};
7 int dp[100001]={0};
8 int i,j,n,cash,npack,bill,num;
9
10 void deal(int num, int bill)
11 {
12 int k=0,j,t;
13 if(num==1){ npack++; c[npack]=bill; return ; }
14 if(num==2){ npack++; c[npack]=bill; npack++; c[npack]=bill; return ;}
15 for( k=1,j=2*k; 2*j-1<num; k++,j*=2) //j==2^k
16 ;
17 k--;
18 for(j=1,t=0; t<=k; j*=2,t++)
19 {
20 npack++;
21 c[npack]=j*bill;
22 }
23 npack++;
24 c[npack]=(num-j+1)*bill;
25 }
26
27 int main()
28 {
29
30 while(cin>>cash)
31 {
32 memset(dp,0,sizeof dp);
33 memset(c,0,sizeof c);
34 npack=0;
35 cin>>n;
36 for(i=1; i<=n; i++)
37 {
38 cin>>num>>bill;
39 if(num==0)continue;
40 deal(num,bill);
41 }
42
43
44
45 dp[0]=1;
46
47 for(i=1; i<=npack; i++)
48 for(j=cash; j>=c[i]; j--)
49 {
50 dp[j]= dp[j]||dp[j-c[i]];
51 }
52
53 for(j=cash; j>=0; j--)
54 if(dp[j])
55 {
56 cout<<j<<endl;
57 break;
58 }
59 }
60 system("pause");
61 return 0;
62 }
63
64