01,完全,多重,分组

模板

 1 void zero(int weight){
 2     for(int i=1000;i>=weight;i--){
 3         if(dp[i-weight])
 4             dp[i] = 1;
 5     }
 6 }
 7 
 8 void comp(int weight){
 9     for(int i=weight;i<=1000;i++){
10         if(dp[i-weight])
11             dp[i] = 1;
12     }
13 }
14 
15 void dpppp(int weight,int ct){
16     if(weight * ct >= 1000){
17         comp(weight);
18         return;
19     }
20     int t=1;
21     while(t<ct){
22         zero(t*weight);
23         ct -= t;
24         t*=2;
25     }
26     zero(ct*weight);
27 }

 1  for(int k=1;k<=n;k++){
 2         for(int i=m;i>=0;i--){
 3             for(int j=0;j<c[k].size();j++){
 4                 if(i - c[k][j] >= 0){
 5                     if(dp[i] <= dp[i-c[k][j]]+w[k][j]){
 6                         dp[i] = dp[i-c[k][j]]+w[k][j];
 7                         path[k][i] = j + 1;
 8                     }
 9                 }
10             }
11         }
12     }