题目描述

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

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

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

输入格式
第一行两个整数，N，V (0<N≤1000, 0<V≤20000)，用空格隔开，分别表示物品种数和背包容积。

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

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

样例

数据范围
0<N≤1000
0<V≤20000
0<vi,wi,si≤20000
提示
本题考查多重背包的单调队列优化方法。

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

算法1

(单调队列优化dp) $O(NV)$

n个物品， 背包容量为m

假设第i个物品体积为v， 价值为w， 个数为s

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

设m % v = d 变换下上面式子可以得出，

f[i, d]    = f[i-1][d]
f[i, d+v]  = max(f[i-1, d] +w,  f[i-1, d+v])                                    = max(f[i-1, d],  f[i-1, d+v]-w)                                    + w
f[i, d+2v] = max(f[i-1, d] +2w, f[i-1, d+v] +w,  f[i-1, d+2v])                  = max(f[i-1, d],  f[i-1, d+v]-w, f[i-1, d+2v]-2w)                   + 2w
f[i, d+3v] = max(f[i-1, d] +3w, f[i-1, d+v] +2w, f[i-1, d+2v]+w,  f[i-1, d+3v]) = max(f[i-1, d],  f[i-1, d+v]-w, f[i-1, d+2v]-2w,  f[i-1, d+3v]-3w) + 3w
f[i, d+4v] = max(f[i-1, d] +4w, f[i-1, d+v] +3w, f[i-1, d+2v]+2w, f[i-1, d+3v]+w, f[i, d+4v])

我们发现对于体积 j，j % v = d的话，j的状态仅由体积 % v 也等于d的状态转移而来， 比如d+3v, 仅由体积为d+v, d+2v, d这些状态转移， 这些体积 % v都等于d，我们将之前的状态
放入单调队列即可， 放入时，有个技巧，放入 f[i-1, d+ jv] - jw  而不是 f[i-1, d+ jv] ，看看上面的式子就知道为啥了，是为了利用之前的结果。 我们减去再加回来就能保证当前状态最后的答案正确了。

第0次 f[i, d] = f[i-1, d] 入队
第1次 f[i-1, d+v]-w 进队列与队列之前的数字比较
第2次 f[i-1, d+2v]-2w 进队列与队列之前的数字比较
第j次 f[i-1, d+jv]-jw 进队列与之前队列中的数字比较

所以我们枚举i个物品
枚举余数d
枚举j即可， 用于判断体积为d + jv的时候,背包能装满的最大值 由上面式子发现可以用单调队列处理重复项

有个小细节，由于物品个数有限制我们要加个数组存储 队列中状态对应的编号j


#include <iostream>

using namespace std;

const int C_N = 1005, C_V = 20005;

int f[C_N][C_V], queue[C_V], num[C_V];


int main() {
    int N, V;
    cin >> N >> V;

    for (int i = 1; i <= N; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int d = 0; d < v; d ++) {
            int head = 0, tail = -1;
            for (int j = 0; j <= (V-d)/v; j++) {
                int tmp = f[i-1][d + j * v] - j * w;
                while (head <= tail && j - num[head] > s ) head++;
                while (head <= tail && queue[tail] <= tmp) tail--;
                queue[++tail] = tmp;
                num[tail] = j;
                f[i][d + j*v] = queue[head]+ w * j;
            }
        }
    }
    cout << f[N][V];
    return 0;
}

这里我和yxc的代码有不同的地方，y总的第三重循环是直接枚举的体积