背包问题

本文主要是介绍背包问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

背包问题

0/1背包

• 最基础的背包问题

• 有\(n\)件物品和一个容量为\(m\)的背包。第\(i\)件物品的重量是\(w_i\)，价值是\(v_i\)。求解将哪些物品装入背包可在总重量不超过\(m\)的前提下使价值总和最大。

• \(f(i,j)\)表示前\(i\)件物品，背包容量为\(j\)时最大价值

  那么就需要考虑第\(i\)件物品装/不装

  1. 第\(i\)件物品无法装进背包：\(f(i,j)=f(i-1,j)\)，即可获得的最大值不变
  2. 第\(i\)件物品装入背包：\(f(i,j)=f(i-1,j-w_i)+v_i\)，即前\(i-1\)件物品装入容量为\(j-w_i\)的背包（留下\(w_i\)的空间来装第\(i\)件物品）的价值加上第\(i\)件物品的价值
  3. 第\(i\)件物品不装入背包：\(f(i,j)=f(i-1,j)\)，即可获得的最大值不变

  若第\(i\)件物品可以装入背包，那么当前可获得的最大价值为第2、3种情况的最大值

  int f[n+1][m+1];
  for(int i = 1;i<=n;i++){
      for(int j = 0;j<=m;j++){
          if(j < w[i]) f[i][j] = f[i-1][j];
          else f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i])
      }
  }
  int ans = f[n][m];
  

• 例题

  Lg P1048 采药

  将总时间\(T\)视为容量\(m\)，将总草药数\(M\)视为物品件数\(n\)

  将每株草药的采集时间视为重量\(w\)，将草药价值视为\(v\)

  则可以直接套上面的板子

  #include<bits/stdc++.h>
  using namespace std;
  const int N = 1005;
  
  int t,m;
  int dp[N][N];
  int v[N];
  int T[N];
  
  int main(){
  	scanf("%d%d",&t,&m);
  	for(int i = 1;i<=m;i++) scanf("%d%d",&T[i],&v[i]);
  	
      for(int i = 1;i<=m;i++){
  		for(int j = t;j>=0;j--){
  			if(j < T[i]) dp[i][j] = dp[i-1][j];
  			else dp[i][j] = max(dp[i-1][j],dp[i-1][j-T[i]] + v[i]);
  		}
  	}
  	printf("%d",dp[m][t]);
  	return 0;
  }
  

完全背包

• 有\(n\)件物品和一个容量为\(m\)的背包。第\(i\)件物品的重量是\(w_i\)，价值是\(v_i\)。每件物品可以选无数份。求解将哪些物品装入背包可在总重量不超过\(m\)的前提下使价值总和最大。

• 与0/1背包的区别就在于每份物品的数量无限

• \(f(i,j)\)表示前\(i\)件物品，背包容量为\(j\)时最大价值

  那么就需要考虑第\(i\)件物品装/不装

  1. 第\(i\)件物品无法装进背包：\(f(i,j)=f(i-1,j)\)，即可获得的最大值不变
  2. 第\(i\)件物品装入背包：\(f(i,j)=f(i,j-w_i)+v_i\)，即前\(i\)件物品装入容量为\(j-w_i\)的背包（留下\(w_i\)的空间来装第\(i\)件物品）的价值加上第\(i\)件物品的价值
  3. 第\(i\)件物品不装入背包：\(f(i,j)=f(i-1,j)\)，即可获得的最大值不变

  若第\(i\)件物品可以装入背包，那么当前可获得的最大价值为第2、3种情况的最大值

• 与0/1背包的区别在选第\(i\)件物品的时候，是将前\(i\)件物品装包，而不是前\(i-1\)件

• 因为每件物品可以选无数份，所以选更新过的值\(f(i,j-w_i)\)+\(v_i\)

• 模板

  int f[n+1][m+1];
  for(int i = 1;i<=n;i++){
      for(int j = 0;j<=m;j++){
          if(j < w[i]) f[i][j] = f[i-1][j];
          else f[i][j] = max(f[i-1][j],f[i][j-w[i]]+v[i])
      }
  }
  int ans = f[n][m];
  

  在第5行进行了修改

• 例题

• Lg P1616 疯狂的采药

  在本题使用了滚动数组降维否则爆空间

  #include<bits/stdc++.h>
  using namespace std;
  const int N = (1e7+10);
  int t,m;
  
  long long f[N];
  int v[10010];
  int T[10010];
  
  int main(){
  	scanf("%d%d",&t,&m);
  	for(int i = 1;i<=m;i++) scanf("%d%d",&T[i],&v[i]);
      
  	for(int i = 1;i<=m;i++){
  		for(int j = T[i];j<=t;j++){
  			f[j] = max(f[j],f[j-T[i]]+v[i]);
  		}
  	}
  	printf("%lld",f[t]);
  	return 0;
  }
  

滚动数组

• 通过不断覆盖无用的旧数据从而节约空间的操作

• 易知\(\text{dp}\)的第一维\(i\)仅与\(i-1\)有关，在操作\(i\)的时候旧数据\(i-1\)仍在数组中,因此可以压掉第一维

  从前文的两种模型的状态转移方程中可以看出，

  0/1背包需要上一层的数据，而完全背包不需要，且由于\(i\)与\(j\)是两个互不干扰的维度，降维对\(j\)无影响

  因此

  0/1背包使用滚动数组的时候需要倒着枚举

  完全背包使用滚动数组的时候需要正着枚举

• 另外，如果第\(i\)件物品无法装入背包，则状态不需要覆盖

  所以开始覆盖旧数据的最小重量为\(w_i\)

  因此枚举时可以以\(w_i\)开始/结束

• 模板

  int dp[m+1];
  // 01背包
  for(int i = 1;i<=n;i++){
      for(int j = m;j>=w[i];j--){
          dp[j] = max(dp[i],dp[j-w[i]]+v[i]);
      }
  }
  // 完全背包
  for(int i = 1;i<=n;i++){
      for(int j = w[i];j<=m;j++){
          dp[j] = max(dp[i],dp[j-w[i]]+v[i]);
      }
  }
  

多重背包

• \(n\)个物品，每个物品可选至多\(n_i\)个，可不选，每个体积为\(v_i\)，价值为\(w_i\)。
  求总体积不超过\(m\)的情况下能拿走物品总价值的最大值。

• 将至多\(n_i\)个物品全部视为独立的可选取\(n_i\)个物品，使用0/1背包解决

• 优化

  任何一个数都可以被拆分为 \(2^0,2^1,\dots,2^{k-1},d\) 的形式

  因此将每个\(n_i\)进行二进制拆分后，一定可以凑出\(\leq n_i\)的所有数字

  将拆分出来的数\(k_j\)与原价值、原体积相乘，得到一个新的物品

• 模板

  //这里的n，W分别代表n种物品，最大重量为W
  scanf("%d%d",&n,&W);
  int num = 1;
  for(int i = 1;i<=n;i++){
      //v为价值，w为重量，m为个数
  	int v,w,m;
  	scanf("%d%d%d",&v,&w,&m);
      //进行二进制拆分
  	for(int j = 1;j<=m;j<<=1){
  		Val[++num] = j*v;
  		Wei[num] = j*w;
  		m -= j;
  	}
      //此时的m相当于拆分后剩下的d
  	if(m) Val[++num] = v*m,Wei[num]=w*m;
  }
  //01背包滚动数组
  for(int i = 1;i<=num;i++){
  	for(int j = W;j>=Wei[i];j--){
  		f[j] = max(f[j],f[j-Wei[i]]+Val[i]);
  	}
  }
  

分组背包

• \(n\)个物品，体积为\(w_i\)，价值为\(v_i\)。
  所有物品被分为若干组，同组物品最多选一个。
  求总体积不超过\(m\)的情况下能拿走物品总价值的最大值。

• 把每个组当成一个物品，选的时候枚举选哪个物品

  for 所有的组k
  	for j=W..0
  		for 所有的i属于组k
  			f[j]=max(f[j],f[j-w[i]]+v[i])
  

这篇关于背包问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！