前言

因为我的思维水平有点跟不上我的科技水平了，所以来练一练我此前几乎没有开过的板块：动态规划，背包问题作为动态规划的基础，自然是得好好学学的。

多重背包

引入

你有一个容量为 $V$ 的背包，以及 $n$ 种物品。第 $i$ 种物品的体积为 $w_i$，每件价值为 $val_i$，最多有 $c_i$ 件。

你可以选择每种物品若干件放入背包，但同一种物品选择的件数不能超过 $c_i$，且总容量不能超过 $V$。

请你求出在不超过背包容量的前提下，能获得的最大总价值。

思路

我们可以把每件物品，建模为 01 背包问题中的 $c_i$ 件物品，这样就可以进行简单的转移了，但是这样太慢了，我们需要考虑一些性质进行优化。

二进制拆分定理：任意正整数都可以唯一地表示成若干个互不相同的 2 的幂次之和。

我们根据这个定理，就可以像倍增法那样，把数量为 $s$ 的物品按 $1,2,4,8,…$ 进行分组，剩余部分单独成组，就可以表示所有的数了，时间复杂度可以进一步下降到 $O(V·Σlog s)$。

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++) {
    int p=c[i];
    for(int k=1;p>0;k*=2) {
        int b=min(k,p);
        p-=b;
        int W=b*w[i];
        int V=b*val[i];
        for(int j=v;j>=W;j--) {
            dp[j]=max(dp[j],dp[j-W]+V);
        }
    }
}

混合背包

引入

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 $k$ 次。

思路

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了，我们这里结合 一道例题 进行讲解：

有 (n) 种樱花树和长度为 (T) 的时间，有的樱花树只能看一遍，有的樱花树最多看 (A_i) 遍，有的樱花树可以看无数遍。每棵樱花树都有一个美学值 (C_i)，求在 (T) 的时间内看哪些樱花树能使美学值最高。

下面给出解决此类问题的伪代码：

1
2
3
4
5
6
7
8
for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}

对应到这道题来说，也是同理，根据能看的次数就可以判定了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

int dp[1005];

int main() {
    int h1, m1, h2, m2, n;
    scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &n);

    int m = (h2 - h1) * 60 + m2 - m1;

    for (int i = 1; i <= n; i++) {
        int t, c, p;
        scanf("%d%d%d", &t, &c, &p);

        if (p == 0) {
            for (int j = t; j <= m; j++)
                dp[j] = max(dp[j], dp[j - t] + c);
        } else {
            for (int k = 1; p > 0; k *= 2) {
                int x = min(k, p);
                p -= x;

                int w = x * t;
                int v = x * c;
                for (int j = m; j >= w; j--)
                    dp[j] = max(dp[j], dp[j - w] + v);
            }
        }
    }

    printf("%d\n", dp[m]);
    return 0;
}