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