【动态规划】背包问题

前言

根据维基百科 ，背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：

1. 01背包问题
2. 完全背包问题
3. 多重背包问题

此外，还存在一些其他考法，例如恰好装满、求方案总数、求所有的方案等。本文接下来就分别讨论一下这些问题。

前言链接：动态规划之背包问题系列

0-1背包

世上背包千千万，无一不是 01 背包的变体
0-1背包是学习背包问题的开始，是最简单的背包问题。你拥有的每种物品都只有一件，此时只有取与不取两种情况——也就是0和1的区别。

对于容量为V的背包，N件物品（重量为M，价值为W），每一件都可以尝试放入背包中，那么顺序就是遍历这N件物品，每遍历到一个新的物品，都尝试将当前物品放入背包中，看看是放入后得到的价值高还是不放的价值高，取最高者即可。要求所有物品的重量M之和不超过背包的容量V。

0-1背包的一般解是使用一个二维数组$DP[N][V]$存储状态，这个二维数组中的每一个位置$DP[i][j]$代表的意思是前$i$个物品在容量为$j$的时候可以获取的最大价值是多少。状态转移方程是：

$$DP[i][j] = max(DP[i - 1][j - M] + W, DP[i - 1][j])$$

不过这种形式已经过时了。我们很自然的可以发现每次状态转移时只与此时上一个物品，也就是$i-1$和前面的$j-M$有关，在$j$后面的数组是不影响的。那么我们可以直接使用一维数组$DP[V]$来存储状态。对于每一次转移来说，此时未转移的$DP[j]$其实就等价与$DP[i - 1][j]$，我们只是忽略了第一维的$i - 1$。同时注意转移后并不会影响前面状态的转移，所以我们只要从后往前转移就不会对下次转移产生干扰。状态转移方程为：

$$DP[j] = max(DP[j - M] + W, DP[j])$$

伪代码

// 01背包问题伪代码(空间优化版)
// w[i]代表第i件物品的价值
// m[i]代表第i件物品的重量
dp[0,...,V] = 0
for i = 1,...,N // 从选择一件物品到N件物品
    for j = V,...,w[i] // 遍历所有容量(必须逆向枚举!!!)
        dp[j] = max(dp[j], dp[j − w[i]] + m[i])

完全背包

完全背包问题和0-1背包问题不同的地方在于，完全背包的每件物品都是无穷多件，这样我们就不用像0-1背包一样，每次都选择不包括当前物品的背包来尝试添加当前物品（因为每件物品只能添加一次），而是可以在包括当前物品的背包中，选择继续添加当前物品。

而实现完全背包也很简单：还记得刚才我们0-1背包中在j循环要中的逆向枚举的原因吗？因为如果正向枚举会就出现状态$DP[j - w[i]]$已经被转移的情况，也就是还原成二维数组后第一维已经改成i的情况。这与0-1背包的原始转移方程不符，会出现一个物品多次放入的转移。

可现在这个原来的BUG变成了解决完全背包的密码！我们只需要把0-1背包的逆向枚举改成正向枚举就解决了完全背包问题。此时一个状态可以从已经被当前状态转移的状态转移而来，而我们i循环枚举的就是转移的物品，那么换而言之就是一次转移可以放入多个相同的物品。状态转移方程与0-1背包相同：

$$DP[j] = max(DP[j - M] + W, DP[j])$$

伪代码

我们只需要把逆向枚举改成正向枚举即可

// 01背包问题伪代码(空间优化版)
// w[i]代表第i件物品的价值
// m[i]代表第i件物品的重量
dp[0,...,V] = 0
for i = 1,...,N // 从选择一件物品到N件物品
    for j = w[i],...,V // 遍历所有容量(正向枚举)
         dp[j] = max(dp[j], dp[j − w[i]] + m[i])

多重背包

这时候，我们的每种物品除了它的编号I，价值W与重量M之外，我们还引入了一个性质S，代表它的个数。那么问题就变成了：
一共有N种物品，第I（I从1开始）种物品的数量为S，重量为M，价值为W。在总重量不超过背包承载上限V的情况下，能够装入背包的最大价值是多少？

简单暴力的想法就是把第I种物品的S个物品变成编号为$I_{1},I_{2},I_{3}...I_{S}$的S个物品，然后用0-1背包求解，简单可行。

可问题是当N与S极大时，空间与时间就受不了了，毕竟我们的时间复杂度是$O(V * \Sigma S[i])$，$\Sigma S[i]$在$10^5$级别就寄了。

所以我们就要通过我们最开始接触的数据结构——变量里找思路了。为什么一串十六位二进制数就可以表示出$(-2^{16} ～ 2^{16}-1)$的十进制数呢？我们是不是也可以用类似的方法把一种物品用极小的个数拆分呢？

用二进制拆分！

采用二进制思想的时候，把物品分为$2^0，2^1，……，2^k，S-2^{(k+1)}-1$。根据之前变量的联想，很明显这样的二进制组合可以组成1-S的任意数量物品，和一个一个组合是相同的。这种方法的时间复杂度是$O(V * log(\Sigma S[i]))$。

拆分完毕后，就可以使用0-1背包解决多重背包问题了。

下面给出一道例题AC代码做示范：

例题P1776AC代码

题目链接P1776 宝物筛选

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 100005

using namespace std;

int N, V;
int W[MAX]; // 记录价值
int M[MAX]; // 记录重量
int DP[MAX]; // 状态转移数组
int tot; // 记录物品个数

int main()
{
    scanf("%d%d", &N, &V);
    for(int i = 1; i <= N; i++)
    {
        int w, m, s;
        scanf("%d%d%d", &w, &m ,&s);
        for(int j = 1; s - j >= 0; j <<= 1 )  // 二进制拆分优化
        {
            tot++;
            W[tot] = w * j;
            M[tot] = m * j;
            s -= j;
        }
        if(s) // 如果还有剩下的
        {
            tot++;
            W[tot] = w * s;
            M[tot] = m * s;
        }
    }
    //0-1背包
    for(int i = 1;i <= tot; i++)
    {
        for(int j = V; j >= M[i]; j--)
        {
            DP[j] = max(DP[j], DP[j - M[i]] + W[i]);
        }
    }
    printf("%d", DP[V]);
    return 0;
}

混合背包问题

如果将01背包、完全背包、多重背包混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。 就是混合背包问题。

这个问题其实跟01背包、完全背包、多重背包同源，可以使用同一种解决办法，只要在解决问题的时候牢牢记住，无限量的物品实际上等同于背包总容量与单间物品的重量相处所得的件数（最大使用量），因为即使物品数量再多也不可能使用到超过最大使用量的部分，又考虑到件数为1的情况是有限量中的特殊情况，所以，这个问题可以转换为一个多重背包问题，进而又可以通过多重背包问题转换成01背包问题求解。

例题P1883樱花

题目链接：P1833 樱花 - 洛谷

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 100005

using namespace std;

inline int read() 
{
    char ch = getchar();
    int x = 0, cf = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') cf = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') 
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * cf;
}

int T; // 可用的时间之和
int N; // 树的数量
int C[MAX];
int M[MAX];
int DP[MAX];
int tot;

int main()
{
    int t1 ,t2 ,t3, t4;
    t1 = read();
    t2 = read();
    t3 = read();
    t4 = read();
    T = (t3 - t1)  * 60 + t4 - t2;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
    {
        int m, c, p;
        scanf("%d%d%d", &m,  &c, &p);
        if(p == 0)
        {
            tot++;
            C[tot] = c;
            M[tot] = m;
            for(int j = M[tot]; j <= T; j++)
                DP[j] = max(DP[j - M[tot]] + C[tot], DP[j]);
        }
        else
        {
            for(int j = 1; p - j >= 0; j <<= 1 )
            {
                tot++;
                C[tot] = c * j;
                M[tot] = m * j;
                p -= j;
                for(int v = T; v >= M[tot]; v--)
                    DP[v] = max(DP[v - M[tot]] + C[tot], DP[v]);
            }
            if(p)
            {
                tot++;
                C[tot] = c * p;
                M[tot] = m * p;  
                for(int j = T; j >= M[tot]; j--)
                    DP[j] = max(DP[j - M[tot]] + C[tot], DP[j]);
            }
        }
    }
    printf("%d", DP[T]);
    return 0;
}