原题链接

多重背包问题三

与完全背包问题的不同

• $完全背包问题: 可以找到f[i][j] 和 f[i][j - v[i]]之间的密切关系: f[i][j - v[i]] + w[i] —> f[i][j]$
  $所以我们在两重循环下依次枚举物品和体积只要状态合法(j >= v[i] 至少要装下一个物品) 不装该物品就是f[i - 1][j]$
  $所以这样枚举下去所有方案不重不漏一次取max得到最终答案$
  $可以得到那个状态转移方程的依据我认为是: 1, 背包容量有限，2, 每个物品的数量是无限的$
  $所以每个物品在背包中最大能装入的数量是确定下来的 所以有:$

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

 这两个方程中的s是一个s， 就是背包所能装下i物品的最大数量.
 这也是为什么两个方程能合并成为f[i][j] = max(f[i][j], f[i][j - v] + w)(在j > v[i])的原因之一

多重背包问题的优化思路

• $但是多重背包问题不同$
  $因为每个物品的数量是有限的， 所以即使背包是可以装下的， 也可能数量是不够的, 因此有一下方程$

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

$为什么不像完全背包问题一样， 会多出一项呢？$
$原因就是这是多重背包问题， 他给我们的物品的数量是有限制的， 在背包能装下的情况下，$
$即使在j - v的容积下也能装下这s件物品$
$那么也就当然会有f[i - 1][j - (s + 1)v] + sw 了$
$而我们要知道的是局部最大值， 而非全局最大值， 而全局最大值无法推导出局部最大值。但是可以发现$

f[i][j - v] = max(f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, ... f[i - 1][j - (s + 1)v] + sw;
f[i][j - 2v] = max(f[i - 1][j - 2v], f[i - 1][j - 3v] + w. f[i - 1][ - 4v] + 2w, ... f[i - 1][j - (s + 2)v + sw);

...

f[i][r + (s - 1)v] = max(f[i - 1][r + (s - 1)v], f[i - 1][r + (s - 2)v] + w ... f[i - 1][r] + (s - 1)w;
f[i][r + sv] = max(f[i - 1][r + sv]. f[i - 1][r + (s - 1)v] + w, f[i - 1][r + (s - 2)v] + 2w. ... f[i - 1][r] +sw;

...

f[i][r] = f[i - 1][r];

$注意：这求的仅仅是第i个物品的f[i][j] 不要把它和求其他物品混淆$

$一些对于该系列方程的解释:$

1. 这里的r是 j % v 的值 --> 抛出一下几个问题:
    1) 为什么r在代码中需要枚举？ 不应该是固定的吗？

    我们在枚举本题中枚举体积的时候是每次 += v 所以每次得到的体积对v取模得到的余数是一样的
    因此我们如果不枚举r我们得到的体积仅仅是一类
    这也说明了我们在把体积分为了mod v 余 0 1 2 ... v - 1 这几类
    对于每一类都用一遍滑动窗口求最值, 最终所求的集合也就是不重也不漏
    并且我们最初的状态是f[i][r] 其实是f[i - 1][r] --> 是可以单独求出来的， 后面的状态可以依次类推得到

    2) 枚举这个r的具体含义是什么呢？

    在上一个问题中顺带说了： 其实就是把所有的以 mod v 分类的集合依次求一遍最大值， 保证不重不漏
    才能得到正确的答案
    依次求得f[i - 1][r]. f[i - 1][r + v], f[i - 1][r + 2v] ... f[i - 1][j - 2v]. f[i - 1][j - v], f[i - 1][j]
    即可最终得到f[i][j]的值， 而这个过程就是滑动窗口求最大值的过程

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20010;

int f[N][M];
int w[M], v[M], s[M];
int q[M];
int n, m;

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

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

    // 这里枚举的是每个物品(从第1 ~ n件物品)
    for (int i = 1; i <= n; i ++) {
        for (int r = 0; r < v[i]; r ++) {// 枚举的就是我们所说的余数 0 1 2 ... v - 1
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i]) {// 体积从r开始 依次 += v
                f[i][j] = f[i - 1][j];

                // j 是当前枚举到的体积, 而 s[i] * v[i] 是把所有物品都装下时的体积
                // if  j - s[i] * v[i] > q[hh] --> 说明当前队头存储的下标已经超出了窗口
                if (hh <= tt && q[hh] < j - s[i] * v[i]) hh ++;

                // (j - q[tt]) / v[i] 表示的就是当前第i和物品存了多少个 再 * w[i] 得到偏移量
                // f[i - 1][j] 是正准备插入窗口的值
                while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j])
                    tt --;

                q[++ tt] = j;

                // 最后把f[i][j] 更新成当前窗口的最大值
                f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }

    cout << f[n][m] << endl;;

    return 0;
}