标签：背包 int 选法 43 集合 算法 体积 物品

背包问题

• 背包问题
  • 0/1 背包问题
  • 完全背包
  • 多重背包
    • 二进制拆分法
  • 分组背包

背包是线性 DP 中一类重要而特殊的模型，本文将其作为单独一部分进行总结整理。

0/1 背包问题

0/1 背包问题的模型如下：
给定 \(N\) 个物品，其中第 \(i\) 个物品的体积为 \(V_i\) ，价值为 \(W_i\) 。有一容积为 \(M\) 的背包，要求选择一些物品放入背包，使得物品总体积不超过 \(M\) 的前提下，物品的价值总和最大。
注意：每件物品最多只用一次

DP问题一般从以下两方面入手：

• 状态表示 \(f(i, j)\) ：考虑清楚需要几维来表示状态，每一个状态的含义是什么
  • DP问题的集合是什么？
    • 所有选法
    • 需要满足以下两个条件：
      1. 只从前 \(i\) 个物品中选
      2. 选出来的物品总体积 \(\le j\)
  • 集合的属性是什么？（Max，Min，数量等）
    • \(f(i,j)\) 存的是所有选法集合中的价值的最大值
• 状态计算：考虑清楚如何一步一步计算出状态，对应于集合的划分
  • 考虑如何将当前的集合划分为更小的子集，能否通过子问题求解出原问题的最优解？划分集合需要遵从"不重不漏"的原则，不漏一定要满足，不重有时可不满足。
  • 0/1背包问题中将 \(f(i,j)\) 表示的所有选法分为两大类:
    • 不包含第 \(i\) 个物品的选法：从 \(1\)～\(i-1\) 中选，总体积不超过 \(j\) 的选法集合，用 \(f(i-1,j)\) 表示
    • 包含第 \(i\) 个物品的选法：从 \(1\)～\(i\) 中选，包含第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(i\) 选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j-V_i) + W_i\) 表示。

则0/1背包问题的状态转移方程为

\[f(i,j) = \max {[f(i-1,j), f(i-1,j-V_i) + W_i]} \]

题目链接:AcWing 2. 01背包问题

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N]; // 存储每件物品的体积和价值
int f[N][N];    // 状态表示

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    // 考虑初始的边界情况，f[0][0~m]表示从前0个物品选，总体积不超过0~m的选法，默认为0
    // 此处f[N][N]声明为全局变量，默认初始化为0，所以无需操作
    
    // 状态计算 f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            // 当v[i] > j时，代表背包放不下第i件物品，此种选法集合为空集
            if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
        
    // 最后输出从前n件物品选择，所占体积不超过m的最大物品价值
    cout << f[n][m] << endl;
    
    return 0;
}

DP的优化：一般都是对DP问题的代码或计算方程做等价变形

本题中由于状态转移方程为：

\[f(i,j) = \max {[f(i-1,j), f(i-1,j-V_i) + W_i]} \]

\(f(i,j)\) 在计算过程中只用到了 \(f(i-1)\) 这一层，所以我们可以用滚动数组来做优化。

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N]; // 存储每件物品的体积和价值
int f[N];    // 状态表示

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    // 考虑初始的边界情况，f[0][0~m]表示从前0个物品选，总体积不超过0~m的选法，默认为0
    // 此处f[N][N]声明为全局变量，默认初始化为0，所以无需操作
    
    // 状态计算 f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
    for (int i = 1; i <= n; i ++ )
        // j 与 j-v[i] 严格小于等于 j，所以我们可以从v[i]开始计算
        // 但是v[i]从前向后枚举会导致新的状态不会由旧状态更新
        // 因为计算f[j]时，f[j-v[i]]在之前第i轮循环已经计算过，为了避免此问题，需要倒序循环更新
        for (int j = m; j >= v[i]; j -- ) {
            // 当v[i] > j时，代表背包放不下第i件物品，此种选法集合为空集
            // f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
        
    // 最后输出从前n件物品选择，所占体积不超过m的最大物品价值
    cout << f[m] << endl;
    
    return 0;
}

完全背包

完全背包问题的模型如下：
给定 \(N\) 种物品，其中第 \(i\) 种物品的体积为 \(V_i\) ，价值为 \(W_i\) ，并且有无数个。有一容积为 \(M\) 的背包，要求选择若干个物品放入背包，使得物品总体积不超过 \(M\) 的前提下，物品的价值总和最大。
注意：每件物品可使用无限多次
此问题与0/1背包问题非常相似，思考方式如下：

• 状态表示 \(f(i, j)\) ：考虑清楚需要几维来表示状态，每一个状态的含义是什么
  • DP问题的集合是什么？
    • 所有选法
    • 需要满足以下两个条件：
      1. 只从前 \(i\) 个物品中选
      2. 选出来的物品总体积 \(\le j\)
  • 集合的属性是什么？（Max，Min，数量等）
    • \(f(i,j)\) 存的是所有选法集合中的价值的最大值
• 状态计算：考虑清楚如何一步一步计算出状态，对应于集合的划分
  • 考虑如何将当前的集合划分为更小的子集，能否通过子问题求解出原问题的最优解？划分集合需要遵从"不重不漏"的原则，不漏一定要满足，不重有时可不满足。
  • 完全背包问题中将 \(f(i,j)\) 表示的所有选法分为 \(k\) 类（此处的 \(k\) 根据物品体积不同会动态变化）:
    • 不包含第 \(i\) 个物品的选法：即从 \(1\)～\(i-1\) 中选，总体积不超过 \(j\) 的选法集合，用 \(f(i-1,j - 0 \times v[i]) + 0 \times w[i]\) 表示
    • 包含 \(1\) 个第 \(i\) 个物品的选法：即从 \(1\)～\(i\) 中选，包含 \(1\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(1\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- 1 \times V_i) + 1 \times W_i\) 表示。
    • 包含 \(2\) 个第 \(i\) 个物品的选法：即从 \(1\)～\(i\) 中选，包含 \(2\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(2\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- 2 \times V_i) + 2 \times W_i\) 表示。
    • 以此类推...
    • 直到最终状态，包含 \(k\) 个第 \(i\) 个物品的选法，此时 \(k \times v[i] \le j,\ \ k+1 \times v[i] > j\)，即从 \(1\)～\(i\) 中选，包含 \(k\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(k\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- k \times V_i) + k \times W_i\) 表示。

所以我们得到状态转移方程：

\[f[i][j] = \max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]) \]

题目链接:AcWing 3. 完全背包问题

利用上面的方程我们可以写出如下的朴素做法(一般会超时)：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    
    cout << f[n][m] << endl;
    
    return 0;
}

对其进行优化，我们观察到状态转移方程展开后：

\[\begin{align*} &f[i][j] = \max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]) \\ &f[i][j] = \max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i] + \dots + f[i-1][j-k*v[i]]+k*w[i]) \\ &f[i][j-v] = \max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+w[i], + \dots + f[i-1][j-k*v[i]]+(k-1)*w[i]) \end{align*} \]

观察得到 \(f[i][j]\) 除了第一项之外的部分，与 \(f[i][j-v[i]]\) 一一对应，并且每一项多一个 \(w[i]\)，于是得到如下状态转移方程：

\[f[i][j] = \max(f[i-1][j], f[i][j-v]+w[i]) \]

于是得到两重循环的优化版代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            if (v[i] <= j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    
    cout << f[n][m] << endl;
    
    return 0;
}

又通过观察状态转移方程我们可以看出 \(f[i][j]\) 的更新只依赖于 \(f[i]\) 这一层的值，所以我们可以将代码的二维优化为一维。不同于0/1背包的一点是，完全背包状态转移过程中不涉及违背线性DP原则的问题，即不需要用前一个阶段的值更新下一阶段，所以不需要倒序循环。优化思路与0/1背包问题相同，不再加以赘述，直接上代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m] << endl;
    
    return 0;
}

多重背包

多重背包问题的模型如下：
给定 \(N\) 种物品，其中第 \(i\) 种物品的体积为 \(V_i\) ，价值为 \(W_i\) ，并且有 \(C_i\) 个。有一容积为 \(M\) 的背包，要求选择若干个物品放入背包，使得物品总体积不超过 \(M\) 的前提下，物品的价值总和最大。

注意：每件物品可使用有限多次
此问题与完全背包问题非常相似，思考方式如下：

• 状态表示 \(f(i, j)\) ：考虑清楚需要几维来表示状态，每一个状态的含义是什么（枚举第 k 个物品选几个）
  • DP问题的集合是什么？
    • 所有选法
    • 需要满足以下两个条件：
      1. 只从前 \(i\) 个物品中选
      2. 选出来的物品总体积 \(\le j\)
  • 集合的属性是什么？（Max，Min，数量等）
    • \(f(i,j)\) 存的是所有选法集合中的价值的最大值
• 状态计算：考虑清楚如何一步一步计算出状态，对应于集合的划分
  • 考虑如何将当前的集合划分为更小的子集，能否通过子问题求解出原问题的最优解？划分集合需要遵从"不重不漏"的原则，不漏一定要满足，不重有时可不满足。
  • 完全背包问题中将 \(f(i,j)\) 表示的所有选法分为 \(k\) 类（此处的 \(k\) 根据物品体积不同会动态变化）:
    • 不包含第 \(i\) 个物品的选法：即从 \(1\)～\(i-1\) 中选，总体积不超过 \(j\) 的选法集合，用 \(f(i-1,j - 0 \times v[i]) + 0 \times w[i]\) 表示
    • 包含 \(1\) 个第 \(i\) 个物品的选法：即从 \(1\)～\(i\) 中选，包含 \(1\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(1\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- 1 \times V_i) + 1 \times W_i\) 表示。
    • 包含 \(2\) 个第 \(i\) 个物品的选法：即从 \(1\)～\(i\) 中选，包含 \(2\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(2\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- 2 \times V_i) + 2 \times W_i\) 表示。
    • 以此类推...
    • 直到最终状态，包含 \(k\) 个第 \(i\) 个物品的选法，此时 \(k \times v[i] \le j,\ \ k+1 \times v[i] > j, \ \ k <= C_i\)，即从 \(1\)～\(i\) 中选，包含 \(k\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(k\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- k \times V_i) + k \times W_i\) 表示。

所以我们得到状态转移方程：

\[f[i][j] = \max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]) \]

利用上面的方程我们可以写出如下的朴素做法(一般会超时)：
题目链接:AcWing 4. 多重背包问题
时间复杂度：\(O(NM*\sum_{i=1}^{N}S_i)\)

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    
    cout << f[n][m] << endl;
    
    return 0;
}

当数据范围较大时，上述的朴素做法会TLE，所以考虑如何优化。

二进制拆分法

众所周知，\(2^0,2^1,2^2,\dots,2^{k-1}\) 这 \(k\) 个 \(2\) 的整数次幂中选出若干个相加，可以表示出 \(0\)~\(2^k-1\)之间的任意整数。进一步地，我们求出满足 \(2^0+2^1+\dots+2^p \le C_i\) 的最大整数 \(p\)，设 \(R_i = C_i-2^0-2^1-\dots-2^p\)，那么：

1. 根据 \(p\) 的最大性，有 \(2^0+2^1+\dots+2^{p+1} > C_i\)，可推出 \(2^{p+1}>R_i\)，因此 \(2^0,2^1,\dots,2^p\) 中选出若干个相加可以表示出 \(0\)~\(R_i\) 之间的任何整数。
2. 从 \(2^0,2^1,\dots,2^p\) 以及 \(R_i\) 中选出若干个相加，可以表示出 \(R_i\)～\(R_i+2^{p+1}-1\) 之间的任何整数。而根据 \(R_i\) 的定义，\(R_i+2^{p+1}-1=C_i\)，因此 \(2^0,2^1,\dots,2^p,R_i\) 选出若干个相加可以表示出 \(R_i\)~\(C_i\) 直接的任何整数。

综上所述，我们可以把数量为 \(C_i\) 的第 \(i\) 种物品拆成 \(p+2\) 个物品，他们的体积分别为：

\[2^0*V_i,2^1*V_i,\dots,2^p*V_i,R_i*V_i \]

这 \(p+2\) 个物品可以凑成 \(0\)~\(C_i*V_i\) 之间所有能被 \(V_i\) 整除的数，并且不能凑成大于 \(C_i*V_i\) 的数。这等价于原问题中体积为 \(V_i\) 的物品可以使用 \(0\)~\(C_i\) 次。该方法仅把每种物品拆成了 \(O(\log C_i)\) 个，效率很高。

题目链接:AcWing 5. 多重背包问题 II

时间复杂度：\(O(NM*\sum_{i=1}^{N}\log S_i)\)

#include <iostream>

using namespace std;

// 1000 * log2000 , N 取 12000
const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;
    
    // cnt统计拆分出的物品数量编号
    int cnt = 0;
    // 将n个物品进行二进制拆分
    for (int i = 1; i <= n; i ++ ) {
        int a, b, s;
        cin >> a >> b >> s;
        
        // 将数量为s的物品拆分1,2,4..2^{p-1},c
        int k = 1;
        while (k <= s) {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0) {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    // 将原问题转换为具有cnt个物品的0/1背包问题
    n = cnt;
    
    // 等价于0/1背包问题(cnt个物品，体积限制为m)，进行处理
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    cout << f[m] << endl;
    
    return 0;
}

分组背包

分组背包问题的模型如下：
给定 \(N\) 种物品，其中第 \(i\) 组有 \(C_i\) 个物品。第 \(i\) 组的第 \(j\) 个物品的体积为 \(V_{ij}\) ，价值为 \(W_{ij}\) 。有一容积为 \(M\) 的背包，要求选择若干个物品放入背包，使得每组至多选择一个物品并且物品总体积不超过 \(M\) 的前提下，物品的价值总和最大。
注意：每组物品中至多只能选择一个

• 状态表示 \(f(i, j)\) ：考虑清楚需要几维来表示状态，每一个状态的含义是什么
  • DP问题的集合是什么？
    • 所有选法
    • 需要满足以下两个条件：
      1. 只从前 \(i\) 组物品中选
      2. 选出来的物品总体积 \(\le j\)
  • 集合的属性是什么？（Max，Min，数量等）
    • \(f(i,j)\) 存的是所有选法集合中的价值的最大值
• 状态计算：考虑清楚如何一步一步计算出状态，对应于集合的划分（枚举第 i 组物品选哪个）
  • 考虑如何将当前的集合划分为更小的子集，能否通过子问题求解出原问题的最优解？划分集合需要遵从"不重不漏"的原则，不漏一定要满足，不重有时可不满足。
  • 完全背包问题中将 \(f(i,j)\) 表示的所有选法分为 \(k\) 类（此处的 \(k\) 根据物品体积不同会动态变化）:
    • 不包含第 \(i\) 组物品的选法：即从前 \(i-1\) 组中选，总体积不超过 \(j\) 的选法集合，用 \(f(i-1,j)\) 表示
    • 包含第 \(i\) 组第 \(1\) 个物品的选法：即从 \(1\)～\(i\) 中选，包含 \(1\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(1\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j-V_{i1}) + W_{i1}\) 表示。
    • 包含第 \(i\) 组第 \(2\) 个物品的选法：即从 \(1\)～\(i\) 中选，包含 \(2\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(2\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- V_{i2}) + W_{i2}\) 表示。
    • 以此类推...
    • 直到最终状态，包含第 \(i\) 组第 \(k\) 个物品的选法，此时 \(k \times v[i] \le j,\ \ k+1 \times v[i] > j, \ \ k <= C_i\)，即从 \(1\)～\(i\) 中选，包含 \(k\) 个第 \(i\) 个物品的选法，总体积不超过 \(j\) 的选法集合。直接求不好求，但其等价于先把 \(k\) 个第 \(i\) 个物品选上，再考虑剩下的体积对应的选法集合，可以用 \(f(i-1,j- V_{ik}) + W_{ik}\) 表示。

所以我们得到状态转移方程：

\[f[i][j] = \max(f[i-1][j], \max \lbrace f[i-1][j-v[i][k]]+w[i][k]\rbrace) \]

题目链接:AcWing 9. 分组背包问题

朴素写法：

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        cin >> s[i];                        // 输入第i组物品的数量
        for (int j = 1; j <= s[i]; j ++ )   // 读入每组中的每一个物品体积与价值
            cin >> v[i][j] >> w[i][j];
    }
    
    // 枚举每一组物品
    for (int i = 1; i <= n; i ++ )
        // 从0开始枚举背包容量
        for (int j = 0; j <= m; j ++ ) {
            // 不选这一组的物品的情况
            f[i][j] = f[i - 1][j];
            // 枚举当前组内的每一件物品
            for (int k = 1; k <= s[i]; k ++ )
                // 当物品体积小于背包容积时才有更新的必要
                if (v[i][k] <= j) 
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
            
    
    cout << f[n][m] << endl;
    
    return 0;
}

维数优化：利用“阶段”线性增长的特征，把物品组数作为DP的“阶段”，只要使用了第 i 组物品，就从第 i 个阶段的状态转移到第 i+1 个阶段的状态。用 j 的倒序循环来控制“阶段 i”的状态只能从“阶段 i-1”转移而来。

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 1; k <= s[i]; k ++ )
                if (v[i][k] <= j) 
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            
    
    cout << f[m] << endl;
    
    return 0;
}

标签：背包,int,选法,43,集合,算法,体积,物品
From： https://www.cnblogs.com/I-am-Sino/p/16970800.html