通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（分治）的方式去解决：动态规划 (Dynamic Programming, DP)

多重背包模型

例题

来源：AcWing04 - 多重背包问题 I - https://www.acwing.com/problem/content/4/

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V\le 100$
$0<v_i,w_i,s_i\le 100$

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例

10

分析 & 代码

暴力解法

多重背包和完全背包的区别就是每一种物品取得数量有一个上限 $s_i$，那么可以直接用完全背包的暴力代码，在第三层循环限制下 $k\le s_i$ 就好了。

• 时间复杂度：$O(N\cdot V^2)$ (最坏情况)
• 空间复杂度：$O(V)$

#include <iostream>
#include <algorithm>

using namespace std;

const int SIZE = 1010;
int N, V;
int v[SIZE], w[SIZE], s[SIZE];
int dp[SIZE];

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

二进制优化

暴力解法中第三层循环从 $1$ 遍历到了 $s_i$，当数据过大时，三层循环会超时，我们需要优化这个遍历过程。先看下面的例子：

一个数 $200$，我们可以将其拆为 $1,2,4,8,16,32,64,73$ 这 $8$ 个数，那么通过这 $8$ 个数的不同取法，我们可以拼凑出 $0\sim 200$ 的所有情况。因为 $1$ 可拼凑 $1$，$1,2$ 可拼凑 $1,2,3$，$1,2,4$ 可拼凑 $1,2,3,4,5,6,7$，以此类推即可得证。

那么对于任意一个数 $N$，我们都能找到一组数 $2^0,2^1,2^2,\cdots ,2^k,N-2^{k+1}+1$，通过这一组数的不同取法拼凑出 $0\sim N$ 的所有数。

通过这种思想，我们改变第三层循环的方式，不去一个一个取物品，而是将物品每 $1$ 个、$2$ 个、$4$ 个……打包，然后分析打包好的包裹的不同取法，即变成了 01-背包问题。

• 时间复杂度：$O(N\cdot \log S\cdot V)$
• 空间复杂度：$O(V)$ (已包含空间优化)

#include <iostream>
#include <algorithm>

using namespace std;

// 需要注意各个数组的大小
const int SIZE_NlogS = 25000, SIZE_V = 2010;
int N, V, idx;
int v[SIZE_NlogS], w[SIZE_NlogS];
int dp[SIZE_V];

int main()
{
    cin >> N >> V;
    // 物品读入
    for (int i = 1; i <= N; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        // 物品打包
        while (k <= s)
        {
            v[++idx] = a * k;
            w[idx] = b * k;
            s -= k;
            k *= 2;
        }
        if (s)
        {
            v[++idx] = a * s;
            w[idx] = b * s;
        }
    }
    // 01-背包问题
    for (int i = 1; i <= idx; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;
    return 0;
}

单调队列优化

对于完全背包问题，我们每轮能够取到的数量 $k$ 没有限制，最大均可取到 $\lfloor \frac{j}{v_i}\rfloor$. 由于这个性质，从 $dp(i,j-v_i)$ 到 $dp(i,j)$ 实际上只新增了最左边的 $dp(i-1,j)$ 一项，就可以得到以下的式子，将第三层循环优化掉：

$$\begin{array}{rl}dp(i,j)& =max\{dp(i-1,j),dp(i-1,j-v_i)+w_i,\cdots ,dp(i-1,j-k{v}_i)+k{w}_i\}\\ dp(i,j-v_i)& =max\{dp(i-1,j-v_i),\cdots ,dp(i-1,j-k{v}_i)+(k-1)w_i\}\\ & \Rightarrow dp(i,j)=max\{dp(i-1,j),dp(i,j-v_i)+w_i\}\end{array}$$

但对于多重背包模型，我们每轮能够取到的数量有上界 $s_i$，那么式子就变成了：

$$\begin{array}{rl}dp(i,j)& =max\{dp(i-1,j),dp(i-1,j-v_i)+w_i,\cdots ,dp(i-1,j-s_i{v}_i)+s_i{w}_i\}\\ dp(i,j-v_i)& =max\{dp(i-1,j-v_i),\cdots ,dp(i-1,j-(s_i+1)v_i)+s_i{w}_i\}\end{array}$$

此时我们会发现，从 $dp(i,j-v_i)$ 到 $dp(i,j)$，不仅左边新增了一项 $dp(i-1,j)$，而且右边少了一项 $dp(i-1,j-(s_i+1)\times v_i)$，因此完全背包的递推式无法在这里使用。

不过，这个式子满足滑动窗口的性质，我们相当于每次都维护一个长度为 $s_i$ 的滑动窗口，求窗口内的最大值。因此可以使用单调递减队列来维护窗口中的最大值。

---

其中，单调递减队列储存 $1\sim V$ 的下标值，队头代表着滑动窗口内对应值最大的下标值。

我们可以发现 $dp(i,j)$ 比 $dp(i,j-v_i)$ 整体多了 $w_i$，即对于不同大小的 $j$，$dp(i,j)$ 存在整体偏移量 $n\cdot w_i$，如果我们要用单调队列维护最大值，必须消除这个偏移量的干扰。我们使用的方法是将每一项统一为下面的格式：

$$\dots \dots ,dp(i,r+3v)-3w,dp(i,r+2v)-2w,dp(i,r+v)-w,dp(i,r)$$

即单调队列比较时使用：$dp(i-1,x)-(x-r)/v_i\times w_i$

• 时间复杂度：$O(N\cdot V)$
• 空间复杂度：$O(V)$ (已包含空间优化)

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int main()
{
    int N, V;
    cin >> N >> V;
    vector<int> v(N + 10), w(N + 10), s(N + 10);
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i] >> s[i];
    vector<int> dp(V + 10), lst(V + 10), que(V + 10);
    for (int i = 1; i <= N; i++)
    {
        lst = dp;
        for (int r = 0; r < v[i]; r++)
        {
            int hh = 0, tt = -1;
            for (int k = r; k <= V; k += v[i])
            {
                if (hh <= tt && que[hh] < k - s[i] * v[i])
                    ++hh;
                while (hh <= tt && lst[que[tt]] - (que[tt] - r) / v[i] * w[i] <= lst[k] - (k - r) / v[i] * w[i])
                    --tt;
                if (hh <= tt)
                    dp[k] = max(dp[k], lst[que[hh]] - (que[hh] - k) / v[i] * w[i]);
                que[++tt] = k;
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

分组背包问题

例题

来源：AcWing09 - 分组背包问题 - https://www.acwing.com/problem/content/9/

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 $N，V$，用空格隔开，分别表示物品组数和背包容量。

接下来有 $N$ 组数据：

• 每组数据第一行有一个整数 $S_i$，表示第 $i$ 个物品组的物品数量；
• 每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij},w_{ij}$，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V\le 100$
$0<S_i\le 100$
$0<v_{ij},w_{ij}\le 100$

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例

8

分析

实际仍然能当作“01-背包问题”来看，只不过“01-背包问题”的每一个物品变成了一组物品，不过我们只用遍历这一组，求到这一组物品的最优情况即可。

• 时间复杂度：$O(V\cdot \sum S)$
• 空间复杂度：$O(V)$ (已包含空间优化)

#include <bits/stdc++.h>

using namespace std;

const int SIZE = 110;
int N, V;
int v[SIZE][SIZE], w[SIZE][SIZE], S[SIZE];
int dp[SIZE];

int main()
{
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
    {
        cin >> S[i];
        for (int j = 0; j < S[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 0; i <= N; i++)
        for (int j = V; j >= 0; j--)
            for (int k = 0; k < S[i]; k++)
                if (v[i][k] <= j)
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
    cout << dp[V] << endl;
    return 0;
}

混合背包问题

例题

有 $N$ 种物品和一个容量是 $V$ 的背包。

物品一共有三类：

• 第一类物品只能用 $1$ 次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用 $s_i$ 次（多重背包）；

每种体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N$，$V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

• $s_i=-1$ 表示第 $i$ 种物品只能用 $1$ 次；
• $s_i=0$ 表示第 $i$ 种物品可以用无限次；
• $s_i>0$ 表示第 $i$ 种物品可以使用 $s_i$ 次；

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V\le 1000$
$0<vi,wi\le 1000$
$-1\le s_i\le 1000$

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例

8

分析

对于混合背包问题，我们的处理方式其实就是对于每一个物品对应的背包模型，使用对应的处理方式。

对于完全背包，我们直接用完全背包的计算方式即可。对于多重背包问题，我们使用二进制优化方式转化为 0-1 背包问题，与 0-1 背包一起统一处理即可。

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

void solve()
{
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 10);
    for (int i = 1; i <= N; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == 0) // 完全背包
        {
            for (int j = v; j <= V; j++)
                dp[j] = max(dp[j], dp[j - v] + w);
        }
        else // 0-1背包 和 多重背包
        {
            s = abs(s); // 一律当多重背包转化成0-1背包
            vector<int> vv, ww;
            int k = 1;
            while (k <= s)
            {
                vv.push_back(v * k);
                ww.push_back(w * k);
                s -= k;
                k *= 2;
            }
            if (s)
            {
                vv.push_back(v * s);
                ww.push_back(w * s);
            }
            for (int j = 0; j < vv.size(); j++)
                for (int k = V; k >= vv[j]; k--)
                    dp[k] = max(dp[k], dp[k - vv[j]] + ww[j]);
        }
    }
    cout << dp[V] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}