背包问题全类型

背包问题

   给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

    背包问题大体都可以用上述方式进行描述，但在具体的问题上有了不同的限制条件，于是便有了各种类型的背包问题。背包问题可基本分为0-1背包问题、部分背包问题、多重背包问题、完全背包问题四大类。接下来我们就分别对四种问题加以分析。
      从四种问题的解决的核心算法可以把部分背包问题单独化为一类，其核心算法为贪心。其余的三种背包问题都可以用动态规划解决。造成部分背包问题与其他的背包问题最大不同的原因是其限定条件的不同，部分背包问题的每件物品可以再进行分化，而其他三种背包问题只在物品数量上做出规定，物品不可再分。我们则按照由特殊到一般，由易到难的顺序分别介绍这四种背包问题。

1. 部分背包问题

限定条件：

    每件物品可以只选取一部分

完整问题描述：

   有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品可以进行分割，分割后的价值按取走重量占该物品总重量的比值计算。在不超过最大承载量 C 的范围内，问最大可以取走的价值为多少？

( 其中 i ∈ {1,2,3,···,n} )

算法：

     贪心

分析：

    根据本题的特殊性，我们可以任意地对某一部品进行分割，所以我们优先选择性价比高的物品，即单位重量下物品的价值。

解题代码

//C++#include<cstdio>#include<algorithm>#include<iostream>using namespace std;struct bag { int w,v; //w表示重量 v表示价值 double p; //用来储存v/w 性价比}a[10005];bool cmp(bag x,bag y) { return x.p > y.p; //性价比高的物品排在前面}int main() { int n,c; cin>>n>>c; //输入物品件数n和最大承载力t for(int i = 0; i < n; i++){ cin>>a[i].w; //输入n个物品的重量 } for(int i = 0; i < n; i++){ cin>>a[i].v; //输入n个物品的价值 a[i].p = (double)a[i].v/a[i].w; //计算每个物品的性价比 } sort(a,a+n,cmp); //对性价比进行排序 double ans = 0.0; for(int i = 0; i < n && t; i++) { //循环条件要附加上c承载力有剩余 if(c >= a[i].w) { //可以完全选择该物品 ans += a[i].v; //取走该物品的全部价值 c -= a[i].w; //承载力减掉物体重量 } else { //剩余承载力不足以取走全部的该物品 ans += t*a[i].p; //按照性价比进行分割 c = 0; //承载力无剩余 } } printf('%.2f\n', ans); //输出答案 return 0;}

注意

计算时注意数据类型

    在计算“性价比”的时候要注意，在C/C++等一部分语言中存在以下机制 int/int = int ，这样是无法计算出小数的，需要将其中任意一项浮点化即可。

2. 0-1背包问题

限定条件：

    每件物品有且仅有一件

完整问题描述：

   有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品有且只有一件。在不超过最大承载量 C 的范围内，问最大可以取走的价值为多少？

( 其中 i ∈ {1,2,3,···,n} )

算法：

    递归、动态规划

分析：

    物品不可进行分割，不可再像部分背包问题一样选择性价比高的物品。举个例子，背包容量为10

物品	A	B	C
重量	8	7	3
价值	16	12	5
性价比	2	1.71	1.67

若按照性价比回西安选择物品A，此时无法再选择物品B或物品C，背包总价值为16。但如果我们选择物品B和物品C，背包的价值为17，后者更优。

  每件物品只有选择或不选择两种状态，这像极了二进制的0和1，选择即1不选即0，故得名0-1背包问题。

   我们先来说说递归算法，通过反复的递与归模拟每件物品选与不选两种状态最后算出最优解。不难得出时间复杂度为O(N^2)。

     这样大的时间复杂度在物品数量较多时无法高效的完成计算。我们需要一种更为高效的算法——动态规划。动态规划可以在O(N*C)的时间复杂度下完成计算，其基本思想是令表示在前个物品中能够装入容量为的背包中的物品的最大值。这句话看起来很难理解，在这里我想提一本书《算法图解》，作者是Aditya Bhargava，我也在这本书上学会了背包问题的动态规划状态。

递归代码

//c++#include<cstdio>#include<algorithm>#define MAXN 10005using namespace std;int n,c,u[MAXN],v[MAXN];  //n-物品数量  c-背包容量  u[i]第i件物品的重量  v[i]第i件物品的价值 int ans;  //答案//dfs参数含义  void dfs(当前物品编号，已选中物品重量总和，已选中物品价值总和) void dfs(int i,int weight,int sum) {      if(weight > c) {   //若选中物品重量总和大于背包总容量及时返回     return;  }  if(i == n) {    //当n件物品全部选择完毕后更新答案并返回     ans = max(ans,sum);    return;  }  dfs(i+1,weight,sum);    //不选择第i件物品步  dfs(i+1,weight+u[i],sum+v[i]);   //选择第i件物品  return;}int main() {  scanf('%d%d',&n,&c); //分别输入物品总数及背包容量   for(int i = 0; i< n; i++) {    scanf('%d%d',&u[i],&v[i]);  //输入每件物品的重量及价值   }  dfs(0,0,0);  //开始递归   printf('%d\n',ans);  //输出答案   return 0;}

动态规划代码

//c++#include<cstdio>#include<algorithm>using namespace std;int n,c; //n-物品总数 c-背包容量 int w,v;  //w-物品重量  v-物品价值 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d',&w,&v);    for(int j = 1; j <= c; j++) { if(j >= w) //当前容量足以承载此物品 dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v); //选此物品与不选进行比较得出较优解 else //当前容量不足以承载此物品 dp[i][j] = dp[i-1][j]; } } printf('%d\n',dp[n][c]); //输出答案 return 0;}

当然，0-1背包问题还有许多优秀的算法可以解决，如记忆化搜索等等。选择了递归和动态规划是因为递归最为简单，而动态规划解法为后面两个背包问题进行了铺垫。记忆化搜索确实是一门很实用的算法，在思维程度上没有动态规划复杂，在效率上有可以和动态规划相媲美。

3.完全背包问题

限定条件：
    每件物品都有无限个

完整问题描述：
    有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且没见物品有无限多个。在不超过最大承载量 C 的范围内，问最大可以取走的价值为多少？
( 其中 i ∈ {1,2,3,···,n} )

算法：
    动态规划

分析：
    和0-1背包问题对比一下，不难发现不同的地方在于0-1背包问题中，每件物品每件物品最多只能选择一次，而在完全背包问题中，每件物品可以选择任意件。
    试着在0-1背包问题的状态转移方程的基础上进行修改，发现只有在每见物品选取的个数上有了变化，不妨定义为这次选取了k倍。修改一下得到状态转移方程，如下

dp[i][j] = max(f[i-1][j-k*u[i]]+k*w[i])  其中，0<=k*u[i]<=c

解题代码

//c++#include<cstdio>#include<algorithm>using namespace std;int n,c; //n-物品总数 c-背包容量 int w,v; //w-当前物品重量 v-当前物品价值 int dp[105][1005];int main(void){ scanf('%d%d',&n,&c); for(int i = 1; i <= n; i++) { scanf('%d%d',&w,&v); for(int j = 1; j <= c; j++) { dp[i][j] = dp[i-1][j]; //先更新状态 for(int k = 1; k*v <= j; k++) //没见物品选k件，但不超过当前容量 dp[i][j] = max(dp[i][j],dp[i-1][j-k*w]+k*v); //进行比较
} } printf('%d\n',dp[n][c]); //输出答案 return 0;}

4. 多重背包问题

限定条件：
    每件物品有有限个

完整问题描述：
    有 n 件物品，第i件物品重 w[i]，价值为 v[i]，有 p[i] 件。在不超过最大承载量 C 的范围内，问最大可以取走的价值为多少？
( 其中 i ∈ {1,2,3,···,n} )

算法：
    动态规划

分析：
    和0-1背包问题和完全背包问题对比一下，不难发现不同的地方在于多重背包问题可以选择多个，但又不能超过某种限制，这种限制就是每件物品的个数是一定的，所以我们只需要在循环里加入这种限制就可以了，即限制k的范围。   

解题代码

    

//c++#include<cstdio>#include<algorithm>using namespace std;int n,c;  //n-物品总数  c-背包容量 int w,v,p;  //w-物品重量  v-物品价值  p-物品个数 int dp[105][1005];int main(void){  scanf('%d%d',&n,&c);  for(int i = 1; i <= n; i++) {    scanf('%d%d%d',&w,&v,&p);    for(int j = 1; j <= c; j++) {      dp[i][j] = dp[i-1][j];  //先更新状态       for(int k = 1; k*v <= j && k <= p; k++)  //没见物品选k件，但不超过当前容量，k也不能超过p          dp[i][j] = max(dp[i][j],dp[i-1][j-k*w]+k*v);   //进行比较 
    }  }  printf('%d\n',dp[n][c]);   //输出答案   return 0;}

到这里背包问题的四种类型就介绍完了，最后感谢大家的关注，让你们久等了！