动态规划-背包问题¶

参考资料：

崔添翼——背包九讲

背包问题整理 https://www.jianshu.com/p/224062fb6ce5

完全背包https://blog.csdn.net/u013480600/article/category/2656071

01背包https://blog.csdn.net/u013480600/article/category/2160339

多重背包https://blog.csdn.net/u013480600/article/category/2668007

OI wiki的总结（背包DP）：https://oi-wiki.org/dp/knapsack/

B站闫雪灿：https://www.bilibili.com/video/BV1Zc4118723

https://www.bilibili.com/video/BV1qt411Z7nE

01背包¶

$O(n^2)$ 空间复杂度算法¶

题面形式：

有 $n$ 个重量和价值分别为 $w_i, v_i$ 的物品，从这些物品中选出总重量不超过 $W$ 的物品，每个物品最多只能选一次，求价值总和最大的方案。进一步思考，如果需要输出方案怎么办？（也就是究竟选了哪些物品）

这里需要提一下，并不是题面符合此形式就一定用01背包来求解，要去看数据范围，如果数据范围很大但是n的数量很小，那么可以考虑《挑战程序设计竞赛》折半枚举里面的超大背包问题。

先考虑一下暴力解法：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n = 20, totalWeight = 20;
vector<int> w(n), v(n);

int zeroOnePack(int i, int weightLeft)
{
    int res;
    if (i == n) res = 0; //没有剩余物品了
    else if (weightLeft < w[i]) 
        res = zeroOnePack(i + 1, weightLeft); //剩余容量放不下当前物品，考虑下一个
    else //当前物品可以放下，选和不选都尝试一下
        res = max(zeroOnePack(i + 1, weightLeft), zeroOnePack(i + 1, weightLeft - w[i]) + v[i]);

    return res;
}

int main()
{
    cin >> n >> totalWeight;

    for (int i = 0; i < n; ++i) cin >> w[i] >> v[i];
    cout << zeroOnePack(0, totalWeight) << endl;
}

这个程序主要是针对POJ 3624的测试数据，即使开的数组大一些也会超时的，因为对于每个物品存在选择和不选择两种情况，那么时间复杂度是 $O(2^n)$ ，优化的办法就是去记录已经计算过的结果，方便下次利用。

程序方面最好在《算法手写代码必备手册》的基础上来完善，解这种问题的关键是先写出**状态转移方程**，用空间复杂度不是很理想的二维数组来存储，然后根据表达式再用一位数组（也就是常说的滚动数组）来进行优化。

状态转移方程的两个关键点：写出完整的表达式，明确表达式参数的意义。

定义状态转移方程 $f[i][j]$ 表示把前 $i$ 个物品放进容量为 $j$ 的背包所能获得的最大价值。 $$ f[i][j]=\max {f[i-1][j], f[i-1][j-w[i]]+v[i]} $$ 表达式的含义：

第 $i$ 个装不进去，价值为 $f[i-1][j]$
第 $i$ 个装进去了，价值为 $f[i-1][j-w[i]] + v[i]$ 。

下面的程序针对的都是POJ3624的，HDU2602和此基本上是一模一样的。

//二维数组存储的版本
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n = 3402, totalWeight = 12880;
vector<int> w(n + 1), v(n + 1);
vector<vector<int>> f(n + 1, vector<int>(totalWeight + 1));

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


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> totalWeight;

    for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
    cout << zeroOnePack() << endl;
}

滚动数组优化空间复杂度¶

但是上面的程序提交会发现超过内存限制，因为开数组要 $N(3403)\times M(12881)$ 的二维数组，相比于HDU的题目数据大了很多。所以该考虑一下利用滚动数组进行优化了。 $$ f[i][j]=\max {f[i-1][j], f[i-1][j-w[i]]+v[i]} $$ 使用滚动数组的方法并不一定好理解，不妨从数学形式来看，对于 $f[i][j]$ 的求解，始终需要去访问 $f[i-1]*$ ，其中*代表状态转移方程中的两种形式，也就是说，二维的表示可以退化成一维的。即可以用 $f[j]$ 来表示。 $f[j] = max(f[j], f[j - boneWeight[i]] + boneValue[i])$ ，但是需要考虑遍历的顺序。这里是逆序遍历，保证每个物品最多使用一次，如果顺序遍历，则是完全背包问题。

解释一下为什么顺序遍历就会出现可能多次存储的情况，因为要考虑的是针对01背包这一类问题的解法，考虑**如果还是顺序遍历**，程序的核心代码是：

vector<int> d(totalWeight + 1, 0);
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= totalWeight; ++j) {
        d[j] = max(d[j], d[j - w[i]] + v[i]);
    }
}

所以可能存在 $j - 2w[i]\geq0$ 的情况，所以在计算 $d[j-2*w[i]]$ 对应的值的时候，用到了 $d[j - w[i]]$ 的结果，那么就意味着第 $i$ 个物品被放入了2次，所以违背了题意。逆序的时候， $d[totalWeight]$ 只与 $d[totalWeight], d[totalWeight-w[i]] + v[i]$ 有关，所以不会存在重复计算的过程。时间复杂度 $O(nW)$

//滚动数组优化
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n = 3402, totalWeight = 12880;
vector<int> w(n + 1), v(n + 1);

int zeroOnePack()
{
    vector<int> d(totalWeight + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = totalWeight; j >= w[i]; --j) {
            d[j] = max(d[j], d[j - w[i]] + v[i]);
        }
    }
    return d[totalWeight];
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> totalWeight;

    for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
    cout << zeroOnePack() << endl;
}

初始化细节¶

《背包九讲》里提到，主要针对题目要求背包恰好装满的时候的最优解。这种情况下除了d[0] = 0，其他的都初始化为INT_MIN，理解就是在什么都不放的情况下，只有背包容量为0的时候存在合法解，也就是0，其他部分初始化为负无穷大，代表初始时无合法解。

如果并未说背包完全填满，则初始时每个都有一个合法解，也就是什么都不装，所以就可以初始化为0.

二维01背包¶

HDU-3496 Watch the movie（二维01背包）
洛谷P1855 榨取kkksc03（二维01背包）

以HDU-3496 Watch the movie为例：共有n个影碟，每个影碟能够增加快乐值 $v_i$ ，影碟需要占用的时间是 $c_i$ ，但是只能选择 $m$ 个影碟，看 $L$ 分钟，问如何在限制下让快乐值最大？

分析：这里存在两个限制条件，并且每个物品只有一个，相当于增加了一个维度的01背包，用d[i][j][k]代表从前i个物品选出j个且总时间不超过k的最大价值，利用滚动数组优化后，状态转移方程是： $$ d[i][j] = \max(d[i][j], d[i - 1][j - w[i]] + value[i]) $$

//HDU-3496 Watch the movie
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, volume;
vector<vector<int> > d(105, vector<int>(1005, INT_MIN));
vector<int> cost(105), value(105);

int twoDimensionZeroOnePack()
{
    fill(d[0].begin(), d[0].end(), 0);
    for (int i = 0; i < n; ++i) {
        for (int j = m; j >= 1; --j) {
            for (int k = volume; k >= cost[i]; --k) {
                d[j][k] = max(d[j][k], d[j - 1][k - cost[i]] + value[i]);
            }
        }
    }

    return d[m][volume] < 0 ? 0 : d[m][volume];
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        cin >> n >> m >> volume;
        for (int i = 0; i < n; ++i) {
            cin >> cost[i] >> value[i];
        }
        cout << twoDimensionZeroOnePack() << endl;

        for (int i = 0; i < n; ++i) fill(d[i].begin(), d[i].end(), INT_MIN);
    }

    return 0;
}

三层循环，时间复杂度是 $O(nmL)$ ，空间复杂度是 $O(mL)$ 。

超大容量背包¶

01背包转多重背包¶

HDU-3732 Ahui Writes Word

这种题目类型一般会出现n和volume很大，但是每个物品的重量要远小于volume，根据鸽巢原理，意味着存在某一重量对应多个物品，于是转化成多重背包问题。

带负数的01背包¶

POJ 2184 Cow Exhibition（带负数的01背包）

带浮点数的01背包¶

HDU-1203 I need an offer（浮点数01背包）

01背包的第K大问题¶

HDU 2639 bone collector II（01背包的第K大问题）

总结¶

在面对01背包的模型的时候，要注意观察条件，先计算时间复杂度再写代码。

比如经典的01背包模型，时间复杂度是 $O(nW)$ 。
超大容量背包的情况（《挑战程序设计竞赛》），需要用折半枚举，一般题目里 $n$ 比较小，时间复杂度 $O(n2^{n/2})$ 。
表面是01背包，实际上是多重背包，比如背包容量较大（ $10^5$ ），物品数量n也较大（ $10^5$ ），但是重量较小（ $10^3$ ），说明会存在很多重复的重量，于是变成多重背包问题，然后用队列优化。（HDU-3732 Ahui Writes Word）
注意题目的迷惑性，比如2020 Google kick star Round A，其实就是简单的贪心，但是题面容易诱导人用背包问题来求解，即使用单调队列优化，时间复杂度也会很大。

典型题目：

完全背包¶

题面形式：

有 $n$ 种重量和价值分别为 $w_i,v_i$ 的物品，每种物品数量无限，从这些物品中挑选总重量不超过 $W$ 的物品，求挑选出的物品价值总和的最大值，进一步的，考虑输出价值最大时的方案（输出路径）

状态转移方程和01背包一致，经上面01背包的分析，其代码只需要正序遍历即可。时间复杂度 $O(nW)$ ，空间复杂度 $O(\max(n, W))$ 。

vector<int> d(totalWeight + 1, 0);
for (int i = 1; i <= n; ++i) {
    for (int j = w[i]; j <= totalWeight; ++j) {
        d[j] = max(d[j], d[j - w[i]] + v[i]);
    }
}

典型题目：

多重背包¶

基本模型：有 $n$ 种物品和一个容量为 $v$ 的背包，第 $i$ 种物品最多有 $M_i$ 件，每一件耗费的空间是 $C_i$ ，价值是 $W_i$ ，求如何使价值总和最大。

优化的思路是采用二进制分组来优化。时间复杂度 $O(W \times\sum \log c[i])$ ，其中n是物品数量。

二进制分组在一些数据较大的时候也会超时，所以用单调队列进行优化。

01背包思路来解决多重背包¶

每个物品 $c_i$ 件，虽然共n种物品，现在看成 $\sum c_i$ 件物品，变成01背包问题来求解。时间复杂度为 $O(W\sum c_i)$ ，性能较差。

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

return d[m];

虽然这种效率很不理想，但是还是写一个题目做个练习。

1269：【例9.13】庆功会

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> d(6005), price(505), value(505), num(505);

int multiPack()
{
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= num[i]; ++j) {
            for (int k = m; k >= price[i]; --k) {
                d[k] = max(d[k], d[k - price[i]] + value[i]);
            }
        }
    }

    return d[m];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> price[i] >> value[i] >> num[i];
    cout << multiPack() << endl;

    return 0;
}

二进制优化的多重背包¶

HDU 2191 买大米（多重背包模板）

时间复杂度 $O(W \times\sum \log c[i])$ ，其中 $c_i$ 代表每种物品的数量

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int money, riceType;
vector<int> d(101, 0);
vector<int> price(101), weight(201), num(101);

void zeroOnePack(int price, int weight)
{
    for (int i = money; i >= price; --i)
        d[i] = max(d[i], d[i - price] + weight);
}

void completePack(int price, int weight)
{
    for (int i = price; i <= money; ++i)
        d[i] = max(d[i], d[i - price] + weight);
}

void multipack(int price, int weight, int num)
{
    if (price * num >= money){
        completePack(price, weight);
        return;
    } 

    int k = 1;
    while (k < num){
        zeroOnePack(k * price, k * weight);
        num -= k;
        k *= 2;
    }
    zeroOnePack(num * price, num * weight);
}

int main()
{
    int caseNum;
    cin >> caseNum;

    while (caseNum--){
        cin >> money >> riceType;

        for (int i = 1; i <= riceType; ++i){
            cin >> price[i] >> weight[i] >> num[i];
        }

        for (int i = 1; i <= riceType; ++i)
            multipack(price[i], weight[i], num[i]);

        cout << d[money] << endl;

        if (caseNum != 0) fill(d.begin(), d.end(), 0);
    }

    return 0;
}

多了一步判断，数量充足就是完全背包，不充足就是01背包。

单调队列优化多重背包¶

来自《算法竞赛进阶指南》P318。物品种类为n，容量为W，时间复杂度为 $O(nW)$ 。

《挑战程序设计竞赛》4.4.2 双端队列的运用，代码相对《算法竞赛进阶指南》更值得参考。

洛谷-P1776 宝物筛选
HDU 1171 Big Event in HDU

假设物品的种类为n，背包容量为m，每个物品的重量为w[i]，价值为value[i]，数量为num[i]，用d[j]代表背包容量为j时所能得到的最大值。则： $$ d[j] = \max_{0 \leq k \leq num[i] \&\& j - k \times w[i] \geq 0} (d[j - k\times w[i]] + value[i]) $$ 在进行状态转移的时候，j的状态只受到j - w[i], j - 2*w[i] ...的影响，对于j-1，其状态和j的状态互不影响，于是我们可以根据j % w[i]的余数进行分组，余数相同的必在一组。现在假设w[i] = 3，那么根据余数可以分成3组：

j	0	1	2	3	4	5	6	7	8	$\cdots$
`j mod w[i]`	0	1	2	0	1	2	0	1	2	$\cdots$

余数（记为a）相同的组成一组，然后重新编号，单独处理：

编号`j`	0	1	2	3	4	5	$\cdots$
对应重量	a	a+w[i]	a+2*w[i]	a+3*w[i]	a+4*w[i]	a+5*w[i]	$\cdots$

如果没有物品数量的限制，则编号为5的可以由编号为0,1,2,3,4状态转移过来，但是因为有数量限制的存在，那么其实相当于增加了一个长度为num[i]的窗口，这个窗口从前往后滑动，然后求取窗口内的最大值，于是想到可以用单调队列来完成这一工作。

我们令： $$ a = j \mod w[i], b = \left[\frac{j-a}{w[i]}\right] \ j = b \times w[i] + a \ 令k^{'} = b - k; \ d\left[j - k\times w[i]\right] + value[i] = d\left[a +k^{'}\times w[i]\right] - k^{'}\times value[i] + a\times value[i] \ 0 \leq k \leq \min(\left[\frac{j-a}{w[i]}\right], num[i]) \ \max(0, b - num[i]) \leq k^{'} \leq b \ $$

//一本通-1269：【例9.13】庆功会
#include <bits/stdc++.h>

using namespace std;

vector<int> price(505), value(505), num(505);
int n, m;
vector<int> dq_pos(6005), dq_val(6005); //模拟双端队列
vector<int> d(6005);

int multiPack()
{
    for (int i = 0; i < n; ++i) {
        //通过余数进行分组
        for (int a = 0; a < price[i]; ++a) {
            int start = 0, end = 0; //双端队列的头尾
            for (int j = 0; j * price[i] + a <= m; ++j) {
                //if (start < end && dq_pos[start] == j - 1 - num[i]) ++start;

                int tmp = d[a + j * price[i]] - j * value[i];
                //保证队列单增
                while (start < end && dq_val[end - 1] <= tmp) --end;
                //新元素加入队列
                dq_pos[end] = j;
                dq_val[end++] = tmp;
                //更新最大值
                d[a + j * price[i]] = dq_val[start] + j * value[i];
                //如果窗口长度大于num[i]，删掉首部元素
                if (dq_pos[start] == j - num[i]) ++start;
            }
        }
    }

    return d[m];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> price[i] >> value[i] >> num[i];

    cout << multiPack() << endl;

    return 0;
}

和LeetCode 239对比，发现29行只需要写成j - num[i]，这个要从窗口长度k的意义来分析，LeetCode 239中窗口长度k是包含当前元素本身的，而我们这里的k表示当前元素前面k个元素转移过来，仍然是让窗口长度为1，那么当j = 1的时候，可以从j = 0转移过来，由于已经处理完成，队列长度又和窗口长度相同，所以这时候需要清空队列了。

多重背包解决存在性问题¶

POJ 1742 Coins（多重背包的存在性问题）

只需要注意初始化问题，核心程序并无太大变化。

01背包转多重背包¶

HDU-3732 Ahui Writes Word

这种题目类型一般会出现n和volume很大，但是每个物品的重量要远小于volume，根据鸽巢原理，意味着存在某一重量对应多个物品，于是转化成多重背包问题。

典型题目：

混合背包¶

实际上就是上面三种问题的结合，有的只能取一次，有的可以取无限次，有的是k次。

只需要注意多重背包的时候用单调队列优化一下。

//1270：【例9.14】混合背包
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> dq_val(205), dq_pos(205), d(205);


void zeroOnePack(int weight, int value)
{
    for (int i = m; i >= weight; --i)
        d[i] = max(d[i], d[i - weight] + value);
}

void completePack(int weight, int value)
{
    for (int i = weight; i <= m; ++i)
        d[i] = max(d[i], d[i - weight] + value);
}

void multiPack(int weight, int value, int num)
{
    fill(dq_pos.begin(), dq_pos.end(), 0);
    fill(dq_val.begin(), dq_val.end(), 0);

    for (int a = 0; a < weight; ++a) {
        int start = 0, end = 0;
        for (int j = 0; j * weight + a <= m; ++j) {
            int tmp = d[a + j * weight] - j * value;
            while (start < end && dq_val[end - 1] <= tmp) --end;
            dq_pos[end] = j;
            dq_val[end++] = tmp;
            d[j * weight + a] = dq_val[start] + j * value;
            if (dq_pos[start] == j - num) ++start;
        }
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> m >> n;
    int weight, value, num;
    for (int i = 0; i < n; ++i) {
        cin >> weight >> value >> num;
        if (num == 0) completePack(weight, value);
        else if (num == 1) zeroOnePack(weight, value);
        else multiPack(weight, value, num);
    }
    cout << d[m] << endl;

    return 0;
}

HDU 1712 ACboy needs your help
洛谷-P1833 樱花
一本通-1270：【例9.14】混合背包

二维费用的背包问题¶

二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种费用。对于每种费用都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。一般题目可能不会直接提示是二维背包，而是在可选择的物品数量上有限制，比如：HDU-3496 Watch the movie

设第i件物品所需的两种费用分别为 $c_i$ 和 $d_i$ ，两种费用可付出的最大价值分别为 $V$ 和 $U$ ，物品的价值为 $w_i$ 。

设 $d[i][j][k]$ 代表前i种物品在背包容量为j和k的条件下的最大价值。状态转移方程： $$ d[i][j][k] = \max(d[i - 1][j][k], d[i-1][j - c_i][k-d_i] + w_i) $$ 然后滚动数组优化一下空间复杂度。

一本通-1271：【例9.15】潜水员
HDU-3496 Watch the movie（二维01背包）
洛谷P1855 榨取kkksc03（二维01背包）

分组背包¶

有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是c[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

相当于把每一组看成一个物品，每个组只能每次选出一个物品，或者一个都不选，就转化成了01背包。伪代码：

for 所有的组k
    for v = V ... 0
        for 所有的i属于组k
            f[v] = max(f[v], f[v - w[i]] + c[i])

一本通-1272：【例9.16】分组背包

//一本通-1272：【例9.16】分组背包
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

int v, n, t;
vector<int> weight(35), value(35);
vector<int> d(205);
vector<vector<int> > group(15, vector<int>(35));

int groupPack()
{
    for (int i = 1; i <= t; ++i) {
        for (int j = v; j >= 0; --j) {
            for (int k = 1; k <= group[i][0]; ++k) {
                int pos = group[i][k];
                if (j >= weight[pos]) {
                    d[j] = max(d[j], d[j - weight[pos]] + value[pos]);
                }
            }
        }
    }

    return d[v];
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> v >> n >> t;
    int k;
    for (int i = 0; i < n; ++i) {
        cin >> weight[i] >> value[i] >> k;
        group[k][++group[k][0]] = i; //记录每个组的物品对应的序号
    }
    cout << groupPack() << endl;

    return 0;
}

有依赖的背包¶

P1064 金明的预算方案

背包问题的方案数¶

这时候物品的价值其实就是物品的数量，但是需要注意题目可能会用贪心的背景来迷惑，比如2020 Google kick start Round A的题目，注意和基础贪心问题里的“最优装载”进行区分。

一本通-1273：【例9.17】货币系统
一本通-1291：数字组合
LeetCode 面试题8.11 硬币

动态规划-背包问题¶

01背包¶

O(n^2)O(n^2)空间复杂度算法¶

滚动数组优化空间复杂度¶

初始化细节¶

二维01背包¶

超大容量背包¶

01背包转多重背包¶

带负数的01背包¶

带浮点数的01背包¶

01背包的第K大问题¶

总结¶

完全背包¶

多重背包¶

01背包思路来解决多重背包¶

二进制优化的多重背包¶

单调队列优化多重背包¶

多重背包解决存在性问题¶

01背包转多重背包¶

混合背包¶

二维费用的背包问题¶

分组背包¶

有依赖的背包¶

背包问题的方案数¶

$O(n^2)$ 空间复杂度算法¶