【算法】动态规划 – 背包问题总结（二）

概述

上一篇博客讲到了背包问题中的01背包问题，今天这篇博客继续介绍背包问题中的完全背包问题。
首先回顾一下背包问题，背包问题解决的是：一共有N件物品，有一个容积为V的背包，第i个物品有两个属性：体积v[i]和价值w[i]，在背包能装下的前提下，能装的物品最大价值是多少。

完全背包

完全背包问题的关键是，每个物品有无限个。

状态转移方程

根据上次求解01背包的思路，求解完全背包也需要分成两个部分，分别是状态表示和状态计算。
所有背包问题的二维状态表示都和01背包问题一样：用f[i, j]表示所有只考虑前i个物品，且总体积不大于j的所有选法。以下的多重背包，和分组背包问题的状态表示将不再赘述。
而完全背包问题的状态计算也可以参考01背包问题。01背包问题是将状态分成了两份，分别是不含i和含i的部分。因此01背包问题的状态转移方程为：f[i, j] = Max(f[i - 1, j], f[i-1, j-vi]+wi)

而完全背包有无限个物品，那么我们可以将状态分成无限份，我们用k来表示第k个状态的计算，那么k=0就表示不含i的情况，f[i, j] = f[i - 1, j]。
而后面的含有1个，含有两个，…，一直到含有无限个的状态，我们来计算第k个状态来表示。和01背包相似的，01背包计算含i的状态是通过减去第i个物品的体积的状态，加上第i个物品的价值得到的。
那么求第k个状态就可以先去掉k个物品i，求Max，再加回来k个物品i的价值。
综上，得到完全背包的状态表示为：f[i, j] = Max(f[i-1, j-v[i]*k] + w[i]*k) (k表示枚举的第i个物品的个数)。

朴素代码实现

根据状态转移方程可以写出完全背包问题的朴素实现代码，如下。

#include <iostream>
#include <algorithm>

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 = 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[m];

    return 0;
}

完全背包问题的优化

根据上面的代码可以看出完全背包问题套了三层循环，时间复杂度还是比较大的。
我们可以根据完全背包的状态转移方程来给代码进行优化。状态转移方程现在计算的是k从0枚举到i的情况，展开来可以写成下面的样子：
f[i, j] = Max(f[i-1, j], f[i-1, j-v]+w, f[i-1, j-2v]+2w, f[i-1, j-3v]+3w, ...])
而f[i, j-v]的状态计算展开如下：
f[i, j-v] = Max( f[i-1, j-v], f[i-1, j-2v]+2w, f[i-1, j-3v]+3w, ...])
对比上下两式，可以发现f[i, j]除了k=0的情况，后面的状态可以用f[i, j-v]+w表示，这样计算完全背包问题的状态时，就不必从k=1一直计算到无限的状态了，只需要用第i层的状态减去一件物品的体积，再加上一件物品的价值即可得出。（上图也有计算步骤）
因此代码可以优化如下。

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

同理根据01背包的二维优化到一维的方法，可以再将二维数组，优化到一维，不过和01背包问题不同的是，完全背包的最大值函数里，是用第i层的状态，因此不需要j从大到小遍历循环，直接从v[i]遍历到m即可。
优化后的代码如下.

#include <iostream>
#include <algorithm>

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

    return 0;
}

近况碎碎念

虽然蓝桥杯刚结束吧，但是最近事情还是有点多，又忙着考研的同时用闲暇时间写写博客也是很惬意的。
背包问题未完待续…