多重背包

关于多重背包的朴素做法，在基础课里有讲到

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

那么如何用单调队列来优化呢？

$r$ : 背包容积$j$除以物品体积$v$的余数
$$r = 背包容积(j) \% 物品体积(v)$$

对于物品$i$而言，放进背包的话背包的容积就会减少$v_i$，如果物品$i$的数量足够多的话，那么用他来填背包的时候，填到无法再放下物品$i$的时侯，背包剩余的空间为$j - k * v_i$，也就是$j \% v_i$。所以说用$1$~$k$个物品$i$来填背包，背包的剩余容积为：$r、r + v_i、r + 2v_i、 r + 3v_i、···、j - v_i、j$。

由于一个物品$i$占$v_i$的体积，所以当背包体积在$j - v_i、j - v_i + 1、j - v_i + 2、···、j - 1$的时候是装不进去一个新的物品$i$的，所以我们只看$r、r + v_i、r + 2v_i、 r + 3v_i、···、j - v_i、j$这些情况就可以。

可以看到，当背包体积$j$在减少$v$的时候，窗口右滑了一格，而题目要求的是这个窗口内元素的的最大值，如果用朴素的DP的话，就会重新再算一遍这个窗口内所有的元素，但是这个窗口只去掉了一个旧元素，加入了一个新元素，其他元素并没有发生变化，所以没有必要再一次计算多余的元素。可以用一个单调队列来维护一个窗口的最大元素。关于单调队列来做滑动窗口的题可以看基础班的视频。

这里不用for(int j = 0; j <= m; j ++)······来枚举背包的容积，而是用$r、r + v_i、r + 2v_i、 r + 3v_i、···、j - v_i、j$来枚举背包的容积。假设一个物品的体积为v，那么背包容积$j$除以物品体积$v$的余数为$0$~$(v - 1)$可以用以下代码来枚举背包容积。

for (int j = 0; j < v; ++ j) {
    for (int k = j; k <= m; k += v) {
}

一些变量的意义：

• s ：滑动窗口的长度（或者说$s * v$是滑动窗口的长度），s是滑动窗口内元素个数。
• q[ ]：存的是窗口内单调递减的元素的下标，队头元素是窗口内最大的元素的值的下标，比如当前维护队列内有两个元素，且f[i][j - v] + w > f[i][j - 2v]那么队头元素q[hh] = j - v而第二个元素q[hh + 1] = j - 2v
• (k - q[hh]) / v * w：由于q[hh]存的是j - sv，而这里用k表示体积那么一共有(k - q[hh]) / v个此物品，他的价值为(k - q[hh]) / v * w

#include <iostream>

using namespace std;

const int N = 1010, M = 20010;

int q[M];  // s的最大值为20000，v的最小值为1，所以队列里面最多是会有200010个元素的
int n, m;
int f[N][M];


int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; ++ i) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; ++ j) {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v) {
                if (hh <= tt && q[hh] < k - s * v) ++ hh;  // 判断单调队列中的最大元素是否已经滑出窗口
                f[i][k] = f[i - 1][k];  // 不放物品i
                if (hh <= tt) f[i][k] = max(f[i][k], f[i - 1][q[hh]] + (k - q[hh]) / v * w);  // 放物品i
                while (hh <= tt && f[i - 1][q[tt]] + (k - q[tt]) / v * w <= f[i - 1][k]) -- tt;  // 更新单调的队列
                q[++ tt] = k;  // 更新单调的队列
            }
        }
    }



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

    return 0;
}

优化成一维：我发现其实优化不优化时间是几乎一样的，个人认为写二维的比较容易理解，没有必要盲目追求优化成一维。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20010;

int q[M];  // s的最大值为20000，v的最小值为1，所以队列里面最多是会有200010个元素的
int n, m;
int f[M], g[M];


int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; ++ i) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; ++ j) {
            int hh = 0, tt = -1;
            memcpy(g, f, sizeof f);  // 用g[]来保存上一次的更新
            for (int k = j; k <= m; k += v) {
                if (hh <= tt && q[hh] < k - s * v) ++ hh;  
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);  
                while (hh <= tt && g[q[tt]] + (k - q[tt]) / v * w <= g[k]) -- tt; 
                q[++ tt] = k;  // 更新单调的队列
            }
        }
    }



    cout << f[m] << endl;

    return 0;
}