题目描述

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

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

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

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

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

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

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

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

算法1

(滑动窗口 + 滚动数组 + 动态规划) $O(n^2)$

C++ 代码

/*
        核心思路： 把背包分成若干份，分成 模 v 余数是0 ，1 ，2， 3.的为一组
        假设  s[i] = 3 就是 背包的数量是3个。
        f[j]   只能  只能在f[j - v] + w  f[j - 2v] + 2w f[j - 3v] + w中取得最大值。
        f[j + v] 只能  在f[j] + w  f[j - v] + 2w   f[j - 2v] + 3w  中更新最大值
        那么就从小到大枚举，当f[j] 的j 的值不能 够达到选一个背包的时候 ， 那么f[j] 就只能 有f[j]来更新最大值
        此时 f[j + v]  可由  f[j]来更新，  f[j + 2v] 可由f[j] 和f[j + v]来更新 
        像这样推下去，就是一个滑动窗口。
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int f[N], g[N], q[N];
int main()
{
    int n, m;  cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof(f));
        //获取一个滚动数组。f[i - 1][j] 就是他的含义。
        for(int j = 0; j < v; j ++)
        {
            //这就是分类 按照j 代表的是余数
            int hh = 0, tt = -1;
            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);
                //  f[k] 代表选 1 2 3。。。  s个的最大值
                while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt--;
                //滑动窗口的最大值 并不是按照完全的数值大小来分类的  而是一个偏移量的最大值
                q[++ tt] = k;
            }
        }
    }

    cout << f[m] << endl;
    return 0;
}