导读

在阅读本文之前，推荐先读一下：
1. 01背包问题

1. 完全背包问题

多重背包问题

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0 < N, V <= 100

0 < vi, wi，si <= 100

Example 1:

Input:
4 5
1 2 3
2 4 1
3 4 3
4 5 2
Output:
10

题解思路 DP

多重背包问题，和完全背包问题，01背包非常相似，差别仅在于每个物品可以有限次的使用，例如第i个物品，仅仅可以使用s[i]次。同样，我们定义

f[i][j] 表示从前i个物品中，选择总体积不超过j的所有物品集合，我们求解的目标是这个集合的最大价值。

那么

0.当我们不选择物品i时,

f[i][j] = f[i - 1][j]

1.当我们选择1个物品i时

f[i][j] = f[i - 1][j - v[i]] + w[i]

2.当我们选择2个物品i时

f[i][j] = f[i - 1][j - 2 * v[i]] + 2 * w[i]

k.当我们选择k个物品i时

f[i][j] = f[i - 1][j - k * v[i]] + k * w[i]

......

s[i].当我们选择s[i]个物品i时

f[i][j] = f[i - 1][j - s[i] * v[i]] + s[i] * w[i]

综上，只要满足 k * v[i] <= j && k <= s[i]，我们从0开始遍历k，可得

f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i])

那么，我们最终要求得的问题最终解即f[n][m]。
根据状态计算，写出代码。

code

#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    const int N = 110;
    int f[N][N] = {0};
    int n = 0;
    int m = 0;
    scanf("%d %d", &n, &m);

    int v[N] = {0};
    int w[N] = {0};
    int s[N] = {0};
    for (int i = 1; i <= n; ++i) scanf("%d %d %d", &v[i], &w[i], &s[i]);

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

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

看起来，除了多加了一点 k <= s[i]的判断，和完全背包没有什么不同。这篇博客只是无聊来凑字数的么？其实，多重背包问题，更有意思的点在于算法时间复杂度的优化方面。

二进制优化

上面的代码显然是一个$O(n^3)$的算法，当数据范围是

0 < N, V <= 100
0 < vi, wi，si <= 100

是可以通过OJ的。因为现代处理器一秒大概可以处理$10^7$ ~ $10^8$次循环，数据范围小于100这个算法是可以接受的。

但如果我们的数据范围改为

0 < N <= 1000
0 < V <= 2000
0 < vi, wi, si <= 2000

就不行了，最差情况下循环量有$10^9$了，这就要求我们必须要优化算法。

如同完全背包一样，我们再次注意观察 f[i][j] 的递推方程, 并思考对应的 f[i][j - v[i]] 的递推方程

1. f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i], ..., f[i - 1][j - s[i] * v[i]] + s[i] * w[i]) 

2. f[i][j - v[i]] = max(      f[i - 1][j - v[i]],        f[i - 1][j - 2 * v[i]] + 1 * w[i], ..., f[i - 1][j - s[i] * v[i]] + (s[i] - 1) * w[i], f[i - 1][j - (s[i] + 1) * v[i]] + s[i] * w[i]) 

这次和完全背包不同，方程2和方程1除了对齐的部分，还多了一项 f[i - 1][j - (s[i] + 1) * v[i]] + s[i] * w[i]，没办法将方程2整体代入方程1，这种优化方法是不可行的，我们只能想其他办法。

题目中，每个背包可以有2000种重量选择。如果我们将这2000种重量的数据一一放入数组中，这道题目就变成了一个有2000种不同重量的01背包问题。

我们的主要优化方向是将2000的数据量变小，这里，我们将采用类似二进制掩码的方式，例如，对于数字7，1-7中的每个数字，可以用掩码

1 = 0x001
2 = 0x010
4 = 0x100

组合而得。换言之，我们可以用1，2，4这三个数字，通过组合的方式，得出本问题中，7种不同重量的背包。
同样的，非$2^n - 1$的数据，比如10种不同重量的背包，可以用1，2，4，3这四个数字组合而成。这样，O(n)级别的数据量，就变成了O(logn)。对于本题，最差情况下的循环量为 $1000 * 2000 * log(2000) <= 2.4 * 10^7$，这就在OJ可以通过的范围内了。

经过这种优化，本题就变成了一个时间复杂度为O(nvlog(si))级别的01背包问题。
我们写出代码，为了方便，使用了vector存储二进制分割后的背包数据。

code

#include <stdio.h>
#include <algorithm>
using namespace std;

struct good {
    int v;
    int w;
};

int main()
{
    int n = 0;
    int m = 0;
    scanf("%d %d", &n, &m);

    vector<good> goods;
    for (int i = 0; i < n; ++i) {
        int v = 0;
        int w = 0;
        int s = 0;
        scanf("%d %d %d", &v, &w, &s);

        for (int k = 1; k <= s; k *= 2) {
            goods.push_back({v * k, w * k});
            s -= k;
        }

        if (s > 0) {
            goods.push_back({v * s, w * s});
        }
    }

    vector<int> f(m + 1, 0);
    for (auto& g : goods) {
        for (int j = m; j >= g.v; --j) {
            f[j] = max(f[j], f[j - g.v] + g.w);
        }
    }

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