DP大作戰—組合背包，dp大作戰背包

DP大作戰—組合背包，dp大作戰背包

題目描述

組合背包：有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。

DD大牛的偽代碼
for i = 1 to N
    if 第i件物品屬於01背包
        ZeroOnePack(F,Ci,Wi)
    else if 第i件物品屬於完全背包
        CompletePack(F,Ci,Wi)
    else if 第i件物品屬於多重背包
        MultiplePack(F,Ci,Wi,Ni)

輸入

第一個數為數據組數n 1<=n<=10

接下來n組測試數據，每組測試數據由2部分組成。

第一行為背包容量V，物品種類數N。1<=V<=30000,1<=N<=200

接下來N行每行三個數為物品價值v，物品重量w，物品件數M。M=233表示物品無限。

1<=v,w<=200, 1<=M<=25

輸出

對於每組數據，輸出一行，背包能容納的最大物品價值

輸入樣例

1
10 3
2 2 233
3 2 1
4 3 3

輸出樣例

13
題目來源：http://biancheng.love/contest/10/problem/F/index
解題思路：
組合背包：0-1背包、完全背包、多重背包。
因此需要結合上述三種背包問題的解決方法來solve組合背包
0-1背包代碼：

1 void Zeronepack(int w,int v)
2 {
3     for(int i=V; i>=w; i--)
4         if(dp[i]<dp[i-w]+v)
5             dp[i]=dp[i-w]+v;
6 }

完全背包代碼：

1 void Compack(int w,int v)
2 {
3     for(int i=w; i<=V; i++)
4         if(dp[i]<dp[i-w]+v)
5             dp[i]=dp[i-w]+v;
6 }

多重背包代碼：

 1 void Multipack(int w,int v,int num)
 2 {
 3     int k;
 4     if(w*num>=V)
 5     {
 6         Compack(w,v);
 7         return;
 8     }
 9     for(k=1; k<num; k<<1)
10     {
11         Zeronepack(k*w,k*v);
12         num-=k;
13     }
14     Zeronepack(num*w,num*v);
15 }

本題組合背包代碼：

 1 #include <bits/stdc++.h>
 2 int dp[30005];
 3 int V,N;
 4 
 5 void Compack(int w,int v)
 6 {
 7     for(int i=w; i<=V; i++)
 8         if(dp[i]<dp[i-w]+v)
 9             dp[i]=dp[i-w]+v;
10 }
11 
12 void Zeronepack(int w,int v)
13 {
14     for(int i=V; i>=w; i--)
15         if(dp[i]<dp[i-w]+v)
16             dp[i]=dp[i-w]+v;
17 }
18 
19 void Multipack(int w,int v,int num)
20 {
21     int k;
22     if(w*num>=V)
23     {
24         Compack(w,v);
25         return;
26     }
27     for(k=1; k<num; k<<1)
28     {
29         Zeronepack(k*w,k*v);
30         num-=k;
31     }
32     Zeronepack(num*w,num*v);
33 }
34 
35 int main()
36 {
37     int kase,v,w,m;
38     scanf("%d",&kase);
39     while(kase--)
40     {
41         memset(dp,0,sizeof(dp));
42         scanf("%d%d",&V,&N);
43         for(int i=1;i<=N;i++)
44         {
45             scanf("%d%d%d",&v,&w,&m);
46             if(m==1)
47                 Zeronepack(w,v);
48             else if(m==233)
49                 Compack(w,v);
50             else
51                 Multipack(w,v,m);
52         }
53         printf("%d\n",dp[V]);
54     }
55     return 0;
56 }