多重背包

 1 #include<iostream>
 2 const int N=110;
 3 using namespace std;
 4 int n,m;
 5 
 6 struct Rice{
 7     int price;
 8     int weight;
 9     int number;
10 }rice[N];
11 int dp[N];
12 //完全背包
13 void CompletePack(int cost,int weight){
14     for(int i=cost;i<=n;i++){
15         dp[i]=max(dp[i],dp[i-cost]+weight);
16     }
17 }
18 //01背包
19 void ZeroOnePack(int cost,int weight){
20     for(int i=n;i-cost>=0;i--){
21         dp[i]=max(dp[i],dp[i-cost]+weight);
22     }
23 }
24 
25 //多重背包
26 void MultiplePack(int cost,int weight,int number){
27     //如果大于等于金额，就按完全背包处理（此时相当于不限定袋数）
28     if(cost*number>=n){
29         CompletePack(cost,weight);
30         return ;
31     }
32     int k=1;
33     while(k<number){
34         ZeroOnePack(k*cost,k*weight);
35         number-=k;
36         k*=2;
37     }
38     ZeroOnePack(number*cost,number*weight);
39 }
40 
41 int main(){
42     int _case;
43     scanf("%d",&_case);
44     while(_case--){
45         scanf("%d%d",&n,&m);
46         memset(dp,0,sizeof(dp));
47         for(int i=0;i<m;i++){
48             scanf("%d%d%d",&rice[i].price,&rice[i].weight,&rice[i].number);
49         }
50         for(int i=0;i<m;i++){
51             MultiplePack(rice[i].price,rice[i].weight,rice[i].number);
52         }
53         printf("%d
",dp[n]);
54     }
55     return 0;
56 }