01背包问题详解

01 背包是一种动态规划问题。动态规划的核心就是状态转移方程，本文主要解释 01 背包状态转移方程的原理。

问题描述

01 背包问题可描述为如下问题：

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

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

原始的 01 背包

01 背包的状态转移方程为

C_{[i][j]} = \max(C_{[i - 1][j]}, C_{[i - 1][j - w[i]]} + v_{[j]})

• i 代表对 i 件物体做决策，有两种方式—放入背包和不放入背包。
• j 表示当前背包剩余的容量。

转移方程的解释：

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

首先将 f 第 0 行和第 0 列初始化为 0，表示不放物体时最大价值为 0。（物体编号从 1 开始）

接下来依次遍历 f 的每一行。如下所示。

for (int i = 1; i <= n; i++)
{
    for (int j = V; j >= 0; j--)
    {
        if (j >= w[i])//如果背包装得下当前的物体
        {
            f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
        }
        else//如果背包装不下当前物体
        {
            f[i][j] = f[i - 1][j];
        }
    }
}

如果背包装得下当前的物体，在遍历过程中分别计算第 i 件物体放入和不放入背包的价值，取其中大的做为当前的最大价值。
如果背包装不下当前物体那么第 i 个物体只有不放入背包一种选择。

• 不放入背包时，第 i 次决策后的最大价值和第 i-1 次决策时候的价值相同。
• 放入背包时：第 i 次决策后的价值为 第 i-1 次决策时候的价值 加上 当前物体的价值 v [j]。

表格举例：

[[自制] 01 背包问题算法动画讲解](https://www.bilibili.com/video/BV1pY4y1J7na?vd_source = bb82e9e2a13d2f171a5a864e6297afb5)

#include <iostream>
#include <vector>
using namespace std;
#define max(N1,N2) N1>N2?N1:N2
int main()
{
    /*
    第一行输入背包容量V和物体的个数n
    接下来有n行，每行包含两个数字，分别为该物体的花费和价值
    */
    vector<int> w, v; // w为花费，v为价值
    vector<vector<int>> f; // f状态矩阵
    int V, n; // V背包容量，n物体数
    while (cin >> V >> n)
    {
        w.clear();
        v.clear();
        f.clear();
        w.push_back(0);
        v.push_back(0);

        // 输入原始数据
        for (int i = 1; i <= n; i++)
        {
            int cur_w, cur_v;
            cin >> cur_w >> cur_v;
            w.push_back(cur_w);
            v.push_back(cur_v);
        }

        // 初始化状态矩阵
        for (int i = 0; i <= n; i++)
        {
            vector<int> buff(V + 1, 0);
            f.push_back(buff);
        }

        // 动态规划过程
        for (int i = 1; i <= n; i++)
        {
            for (int j = V; j >= 0; j--)
            {
                if (j >= w[i])
                {
                    f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
                }
                else
                {
                    f[i][j] = f[i - 1][j];
                }
            }
        }

        // 输出答案
        int ans = f[n][V];
        cout << ans << endl;
    }
    return 0;
}

优化空间复杂度的 01 背包

未优化时候状态转移方程为

f [i][j] = max⁡(f [i−1][j], f [i−1][j−w[i]]+v [j])f [i][j] = max(f [i−1][j], f [i−1][j−w[i]]+v [j])

遍历过程为

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

可以发现如下问题：

1. 状态表 f 的遍历顺序为从第 1 行开始一行一行遍历，且在遍历第 i 行时候不会用到第 i-2 行数据
2. 遍历每一行时候只用到当前容量 j 和 j-w [i] 的数据

优化方法：

f [j] = max⁡(f [j], f [j−w[i]]+v [j])f [j] = max(f [j], f [j−w[i]]+v [j])

for (int i = 1; i <= n; i++)
{
    for (int j = V; j >= 0; j--)
    {
        if (j >= w[i])
        {
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
        else
        {
            f[j] = f[j]; // 无用操作
        }
    }
}

优化关键点：

1. 用单维数组覆盖存储，只需保留上一行数据
2. j 需要 从大到小 遍历（保证使用更新前的数据）
3. 移除无用操作

最终优化版本：

for (int i = 1; i <= n; i++)
{
    for (int j = V; j >= w[i]; j--)
    {
        f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
}

完整代码：

#include <iostream>
#include <vector>
using namespace std;
#define max(N1,N2) N1>N2?N1:N2
int main()
{
    /*
    第一行输入背包容量V和物体的个数n
    接下来有n行，每行包含两个数字，分别为该物体的花费和价值
    */
    vector<int> w, v; // w为花费，v为价值
    vector<int> f; // f状态矩阵
    int V, n; // V背包容量，n物体数
    while (cin >> V >> n)
    {
        w.clear();
        v.clear();
        f.clear();
        w.push_back(0);
        v.push_back(0);

        // 输入原始数据
        for (int i = 1; i <= n; i++)
        {
            int cur_w, cur_v;
            cin >> cur_w >> cur_v;
            w.push_back(cur_w);
            v.push_back(cur_v);
        }

        // 初始化状态矩阵
        f = vector<int>(V + 1, 0);

        // 动态规划过程
        for (int i = 1; i <= n; i++)
        {
            for (int j = V; j >= w[i]; j--)
            {
                f[j] = max(f[j], f[j - w[i]] + v[i]);
            }
        }

        // 输出答案
        int ans = f[V];
        cout << ans << endl;
    }
    return 0;
}