背包问题

本总结为 2024-08-22 19:12 发布的一篇总结，稍加修缮 \(\LaTeX\)

DP解题流程

1.划分子问题：\(dp(i,j)\) 表示第i个阶段，时间不超过j的最大价值。

2.确定状态转移方程：\(dp(i,j)=max(dp(i-1,j),dp(i-1,j-a[i])+b(i))~~~~a(i)\le j \le T\)

3.确定初始值：\(dp(i,j)\) 均为 \(0\)

4.确定遍历顺序：外层从小到大枚举 \(i\) ,对于每一个 \(i\) ，从小到大枚举 \(j\)。

DP使用条件：

1.重复子问题。明显存在，搜索处理不了的原因就是因为太多重复问题。

2.最优子结构。设计 \(dp[i]\) 表示时间不超过 \(i\) 下的 最大价值，显然可以通过前面的子问题转移求出。

3.无后效性。对于每一轮物品的选择，一定是 通过前面的问题修改后面的解，因此无后效性。

01背包

例题： 例15.1-1 采药

问题描述

有一个容量为 \(V\) 的背包，还有 \(n\) 个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积 \(w\) 和价值 \(v\)。

问：如何向背包装物体才能使背包中物体的总价值最大？

解决办法

1. 创建一个状态矩阵f，横坐标 i 是物体编号，纵坐标 j 为背包容量。

2. 当当前背包容量能装得下当前物品，就分为装和不装两种情况：

3. 放入： 第 \(i\) 次决策后的最大价值和第 \(i-1\) 次决策时候的价值是一样的

4. 不放入： 第i次决策后的价值为 第 \(i-1\) 次决策时候的价值 加上 当前物体的价值 \(v(j)\) 。即没放物体之前背包的容量为 \(j - w(i)\) 。

转移方程： f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[j])

代码

1. 普通版本：

空间复杂度： \(\mathcal O(NM)\)

for(int i=1; i<=M; i++)
  for(int j=0; j<=T; j++)
    f[i][j]=f[i-1][j];
        if(T>=a[i]) f[i][j]=max(f[i][j], f[i-1][j-a[i]]+b[i]);

2. 滚动调用：

我们发现当我们在循环中时，永远不会调用 \(f(i-k,j)~~k>2\)，所以我们可反复调用 $ f(0)$ 和 \(f(1)\),可以用 mod 取模 来实现。

空间复杂度： \(\mathcal O(2N)\)

for(int i=1; i<=M; i++)
  for(int j=0; j<=T; j++)
    f[i][j]=f[i-1][j];
        if(T>=a[i&1]) f[i&1][j]=max(f[i&1][j], f[(i-1)&1][j-a[i]]+b[i]);

3. 最终版本：

\(j\) 从背包容量 \(V\) 开始遍历，即从大到小遍历，保证了当前 f[j] 和 f[j - w[i]]里面存的是 i-1 的数据，即等价于 f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i])，从而和优化空间复杂度前状态转移方程的原理一致。

空间复杂度： \(\mathcal O(N)\)

for(int i=1;i<=M;i++)
  for(int j=T;j>=a[i];j--)
    f[j]=max(f[j],f[j-a[i]]+b[i]);

多重背包

题目描述

给定 \(N\) 个物品，个有价值和体积，每种有 \(C\) 个，请问在背包容积 \(M\) 的情况下，背包最大能装的价值。

解决办法

我们可以认为每种有N个 就是 有N个一样的。

代码

朴素版本：

for(int i=1; i<=n; i++){
  for(int l=1; l<=NUM[i]; l++){//每种的数量
    for(int j=m; j>=l*W[i]; j--){
      f[j]=max(f[j], f[j-W[i]]+V[i]);
    }
  }
}

时间复杂度： \(\mathcal O(M\sum_{i=1}^N C_i)\)

升级版本:

假设第i个的数量为C。它可以用一个二进制表示。

我们用13举例: \(13 \to 1101\)，又可以变成，\(2^0+2^2+2^3\)

证明

由\(2^0+2^1+2^2+···+2^p \le C\) 来表示。

设 \(R_i=C-(2^0+2^1+···+2^p)\)

所以可以用\(2^0,2^1,···,2^p,R_i\)可以表示\(R_i~R_i+2^{p+1}-1=C\)

基于二进制进行拆分，时间复杂度：\(\mathcal O(M\sum_{i=1}^N log_2C_i)\)

cin>>n>>m;
for(int i=1; i<=n; i++){
    int a,b,c;cin>>a>>b>>c;
    int t=1;
    while(c>=t){
        W[++cnt]=t*b;
        V[cnt]=t*a;
        c-=t, t<<=1;
    }
    if(c) W[++cnt]=c*b,V[cnt]=c*a;
}

for(int i=1; i<=cnt; i++){
    for(int j=m; j>=W[i]; j--){
        f[j]=max(f[j], f[j-W[i]]+V[i]);
    }
}

cout<<f[m];

完全背包

题目描述

给定 \(N\) 个物品，个有价值和体积，每种有无限个，请问在背包容积 \(M\) 的情况下，背包最大能装的价值。

解决办法

我们设每个，\(v_i\)=体积 , \(w_i\)=价值。

\[ f[i][j] = max \begin{cases} f[i-1][j] & 不选 \\ f[i-1][j-v_i]+w_i & 1项\\ f[i-1][j-2v_i]+2w_i & 2项\\ ··· & ···\\ f[i-1][j-kv_i]+k w_i & k项 \end{cases} \]

所以剩下的：

\[ f(i,j-v_i) = max \begin{cases} f(i-1,j-v_i) & 不选 \\ f(i-1,j-2v_i)+1w_i & 1项\\ f(i-1,j-3v_i)+2w_i & 2项\\ ··· & ···\\ f(i-1,j-(k-1)v_i)+k w_i & k项 \end{cases} \]

所以我们发现 \(f(i,j-v_i)+w_i \to f(i,j)\)

就得到了转移方程：

\[ f(i,j) = max \begin{cases} f(i-1,j) \\ f(i,j-v_i)+w_i \end{cases} \]

代码

cin>>T>>M;
for(int i=1; i<=M; i++) cin>>a[i]>>b[i];
for(int i=1; i<=M; i++)
    for(int j=a[i]; j<=T; j++)
        f[j]=max(f[j], f[j-a[i]]+b[i]);
cout<<f[T];

混合背包

题目描述

题目描述

有 N 种物品和一个容量是 V 的背包。物品一共有三类：

1. 第一类物品只能用1次（01背包）；

2. 第二类物品可以用无限次（完全背包）；

3. 第三类物品最多只能用 \(s_i\) 次（多重背包）；

每种体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输最大价值。

\(s_i\)=−1 表示第 i 种物品只能用1次；

\(s_i\)=0 表示第 i 种物品可以用无限次；

\(s_i\)>0 表示第 i 种物品可以使用 \(s_i\) 次；

实现方法

把三种结合在一起，遇到哪个用哪个。

代码

cin>>n>>m;

for(int i=1; i<=n; i++){
    cin>>W[i]>>V[i]>>NUM[i]; 
    if(NUM[i]==-1) NUM[i]=1; 
}
for(int i=1; i<=n; i++){
    if(NUM[i]==0){
        for(int j=W[i]; j<=m; j++){
            f[j]=max(f[j], f[j-W[i]]+V[i]); 
        }
    }else{
        for(int l=1; l<=NUM[i]; l++){
            for(int j=m; j>=l*W[i]; j--){
                f[j]=max(f[j], f[j-W[i]]+V[i]); 
            }
        }
    }
}
cout<<f[m];

分组背包

问题描述

有 \(N\) 组物品和一个容量是 \(V\) 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 \(v(i,j)\) ，价值是 \(v(i,j)\) ，其中 \(i\) 是组号，\(j\) 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

解决办法

再加一个循环，枚举一组中的每一个数。

代码

cin>>M>>T;
for(int i=1;i<=M;i++) {
    cin>>s[i];
    for(int j=1;j<=s[i];j++) cin>>A[i][j]>>B[i][j];
}
for(int i=1;i<=M;i++){//枚举每一组
    for(int j=T;j>=0;j--){
        for(int k=1;k<=s[i];k++){
            if(j>=A[i][k]) f[j]=max(f[j],f[j-A[i][k]]+B[i][k]);
        }
    }
}
cout<<f[T];

二维费用背包

题目描述

问题描述

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大量，且价值总和最大。 输出最大价值。

解决办法

加一个循环枚举重量

代码

signed main(){
    cin>>M>>N>>V;
    for(int i=1;i<=M;i++) cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=M;i++)
        for(int j=N;j>=a[i];j--)
            for(int o=V;o>=b[i];o--)
                f[j][o]=max(f[j][o],f[j-a[i]][o-b[i]]+c[i]);
    cout<<f[N][V];
    return 0;
}