简单背包问题

背包问题
应用场景
给定 $n$ 种物品和一个背包。物品 $i$ 的重量是 $w_i$ ，其价值为 $v_i$ ，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包的总价值最大？
*01 背包

*01 背包特点：
　　给定 $n$ 种物品和一个背包 ( 每个物品只能选取一个)。物品$i$ 的重量是$w[i]$，其价值为$v[i]$，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？
*状态：
　　$dp[i][j]$ 表示在只能从 $1-i$ 个物品中选择物品并且背包容量大小为 $j$ 的情况下，所能获得的最大价值。
*限制条件
　　• 只能选择物品 1 ~ i
　　• 选择物品的总重量不能超过 $j$
*状态转移方程：
　　$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])$;

*实现：

1）初始化：

1 int n,m; //n表示物品个数，m表示背包容量
2 for (int i = 0 ;i<= m ;i++)
3     dp[0][i] = 0;

2）-1二维数组实现：

1 for (int i = 1;i <= n ;i++){
2     for (int j = 0 ;j<=m ;j++){
3     dp[i][j] = dp[i-1][j];
4     if (j-w[i]>=0)
5         dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
6     }
7 }

2）-2一维数组实现

1 for (int i = 1;i <= n ;i++){
2     for (int j = m ;j>=0 ;j--){
3         if (j-w[i]>=0)
4             dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
5     }
6 }

*完全背包

*完全背包特点

　　给定 $n$ 种物品和一个背包 ( 每个物品选取无限个)。物品 $i$ 的重量是 $w[i]$,其价值为$v[i]$，背包的容量为$C$。应该如何选择装入背包的物品，是的装入背包中物品的总价值最大？
*状态

　　$dp[i][j]$ 表示在只能从 $1-i$ 个物品中选择物品并且背包容量大小为 $j$ 的情况下，所能获得的最大价值。
*限制条件

　　• 只能选择物品 1 ~ i
　　• 选择物品的总重量不能超过 j

*状态转移方程

　　$dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])$;

*实现

1）初始化

1 int n,m; //n表示物品个数，m表示背包容量
2 for (int i = 0 ;i<= m ;i++)
3     dp[0][i] = 0;

2）-1二维数组实现

1 for (int i =1;i <= n;i++){
2     for (int j = 0;j <= m;j++){
3         dp[i][j]=dp[i-1][j];
4         if (w[i]<=j)
5             dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
6     }
7 }

2）-2一维数组实现

1 for (int i =1;i <= n;i++){
2     for (int j = 0;j <= m;j++){
3         if (d-w[i]>=0)
4         dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
5     }
6 }

*多重背包

*多重背包特点

　　给定 $n$ 种物品和一个背包 ( 每个物品选取有限个)。物品 $i$ 的重量是 $w[i]$ ，其价值为$v[i]$，每个物品可以取$k[i]$个，背包的容量为C。应该如何选择装入背包中的物品使得装入背包中的物品总价值最大？

*状态

　　$dp[i][j]$ 表示在只能从 $1-i$ 个物品中选择物品并且背包容量大小为 $j$ 的情况下，所能获得的最大价值

*限制条件

　　• 只能选择物品 1 ~ i
　　• 选择物品的总重量不能超过 j

*状态转移

　　$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i], dp[i-1][j-w[i]*2] + v[i]*2,...)$

*实现

1）初始化

2）-1二维数组实现

 1 for (int i = 1;i <= n ;i++){
 2     for (int j = 0 ;j<=m ;j++){
 3         dp[i][j] = dp[i-1][j];
 4         for (int z = 1 ; z<=k[i]; z++)
 5             if (j-w[i]*z>=0)
 6                 dp[i][j] = max(dp[i][j],dp[i-1][j-z*w[i]]+z*v[i]);
 7             else
 8                 break;
 9     }
10 }

2）-2一维数组实现

1 for (int i = 1;i <= n ;i++){
2     for (int j = m ;j>=0 ;j--){
3         for (int z = 1; z<=k[i] ;z++)
4             if (j-w[i]*z>=0)
5                 dp[j] = max(dp[j],dp[j-z*w[i]]+z*v[i]);
6             else
7                 break;
8     }
9 }

*多重背包问题转化为 01 背包问题
1. p 以下的数字可否由若干不同数字通过组合得到
　　(a) $2^n$- 1 $n$ == 7 二进制: 111111 000001、000010、000100、001000、010000、100000
　　(b) $k$ + $2^n$ -1 < $2^{n+1}$ -1 $n$ == 7
• $2^n$ -1 及以下的数字可以由以下数字表示 000001、000010、000100、001000、010000、100000
• 大于 $2^n$ -1 的数字 $k$ 加上以上 7 个数字组成的数字可以表示任何大于$2^n$ - 1小于等于k+$2^n$-1的数字
2. 代码实现

 1 //num[i] 表示第i种硬币可以取多少次
 2 //w[j] 表示转后为01背包后 只能取一次的硬币的价值与重量
 3 int totlW = 0;
 4 memset(w,0,sizeof w);
 5 for (int i = 0 ;i< 6; i ++){
 6     for(int j=1; j<=num[i]; j<<=1){
 7         w[totlW++]=j*(i+1);
 8         num[i]-=j;
 9         }
10     if(num[i]>0)
11     w[totlW++]=num[i]*(i+1);
12 }

背包问题
HDU 2602
POJ 2063
POJ 1787
UVA 674
UVA 147

第一题是01背包的板子题，就直接放代码了：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 using namespace std;
 7 int t;
 8 int n,m;
 9 int val[10000],w[10000],f[100000];
10 int main ()
11 {
12     scanf ("%d",&t);
13     while (t--)
14     {
15         scanf ("%d%d",&n,&m);
16         memset(f,0,sizeof(f));
17         for (int i = 1;i <= n;i++)
18             scanf ("%d",&val[i]);
19         for (int i = 1;i <= n;i++)
20             scanf ("%d",&w[i]);
21         for (int i = 1;i <= n;i++)
22             for (int j = m;j >= w[i];j--)
23                 f[j]=max(f[j],f[j-w[i]]+val[i]);
24         printf ("%d
",f[m]);
25     }
26     return 0;
27 }

第二道题是完全背包，因为每个债券都是1000的倍数，所以我们可以直接把总钱数和债券的数额都直接除以1000.因为每年都会有利息，所以每年的总钱数会增加，求出每一年的最大利益，总钱数加上最大利益就是下一年的总钱数。所以，我们只需要对于每一年的总钱数求一个完全背包，每年更新总钱数就好。代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 using namespace std;
 7 const int N = 100100;
 8 int dp[N];
 9 int num[N], val[N];
10 int main()
11 {
12     int t;
13     scanf("%d", &t);
14     while(t--)
15     {
16         int money,year,d;
17         scanf("%d %d", &money, &year);
18         scanf("%d", &d);
19         for(int i=0;i<d;i++)
20         {
21             scanf("%d %d", &num[i], &val[i]);
22             num[i]/=1000;
23         }
24         int sum=money;
25         for(int i=0;i<year;i++)
26         {
27             memset(dp,0,sizeof(dp));
28             money=sum;
29             money/=1000;
30             for(int j=0;j<d;j++)
31             {
32                 for(int k=num[j];k<=money;k++)
33                 {
34                     dp[k]=max(dp[k-num[j]]+val[j],dp[k]);
35                 }
36             }
37             sum+=dp[money];
38         }
39         printf("%d
",sum);
40     }
41     return 0;
42 }

第三题是完全背包+路径输出，$dp[j]$表示总价格为$j$时最多可以有多少个硬币，但是需要维护一下硬币的个数，实际上在01背包中，我们对所有状态都更新了一次答案，这里我们等于是对4种硬币各跑一次背包，维护一下使用次数即可。$used[j]$表示总价格为j时用了多少个某个硬币。$pre[j]$记录方案，表示j出现更有的答案时是由哪个状态转移来的。最后遍历一下输出答案就好了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 using namespace std;
 4 int dp[10005], used[10005], pre[10005], coin[4] = {1, 5, 10, 25}, num[4], ans[26];
 5 int main(){    
 6     int p;    
 7     while(scanf("%d %d %d %d %d", &p, &num[0], &num[1], &num[2], &num[3]) != EOF){        
 8         if(p + num[0] + num[1] + num[2] + num[3] == 0) return 0;        
 9         for(int i = 0; i <= p; ++i){            
10             dp[i] = -1e9;        
11         }        
12         memset(pre, 0, sizeof(pre));        
13         pre[0] = -1;        
14         dp[0] = 0;        
15         for(int i = 0; i < 4; ++i){            
16             memset(used, 0, sizeof(used));            
17             for(int j = coin[i]; j <= p; ++j){                
18                 if(dp[j] < dp[j - coin[i]] + 1 && used[j - coin[i]] < num[i]){                    
19                     used[j] = used[j - coin[i]] + 1;                    
20                     dp[j] = dp[j - coin[i]] + 1;                    
21                     pre[j] = j - coin[i];                
22                 }            
23             }        
24         }        
25         if(dp[p] <= 0){            
26             printf("Charlie cannot buy coffee.
");            
27             continue;        
28         }        
29         memset(ans, 0, sizeof(ans));        
30         while(1){            
31             if(pre[p] == -1) break;            
32             ans[p - pre[p]]++;            
33             p = pre[p];        
34         }        
35         printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
", ans[1], ans[5], ans[10], ans[25]);    
36     }
37 }

第四题一个简单的动态规划，比如要求55的组成方案数，必须要知道55-1=54的方案数和 55-5=50的方案数，和50-10=45的方案数和55-25=30的方案数和55-50=5的方案数，所以dp以此类推，每次更新dp。

 1 #include <cstring>
 2 #include <iostream>
 3 #include <cstdio>
 4 using namespace std;
 5 int f[10000];
 6 int main ()
 7 {
 8     int v;
 9     while(cin>>v){
10         memset(f,0,sizeof(f));
11         int c[6]={0,1,5,10,25,50};
12         f[0]=1;
13         for(int i = 1; i <= 5; ++i)
14             for(int j = c[i]; j <= v; ++j)
15             {
16                 f[j] = f[j]+f[j-c[i]];
17             }
18         cout << f[v]<<endl;
19     }
20     return 0;
21  }