背包问题

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])