AcWing 6：多重背包问题 III ← 单调队列优化

​【题目来源】
https://www.acwing.com/problem/content/6/

【题目描述】
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

【输入格式】
第一行两个整数，N，V（0＜N≤1000，0＜V≤20000)，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi，wi，si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

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

【输入样例】
4 5
1 2 3
2 4 1
3 4 3
4 5 2

【输出样例】
10

【数据范围】
0<N≤1000，
0<V≤20000，
0<vi, wi, si≤20000

【算法分析】
● 代码 memcpy(dest, src, sizeof(src)); 将整个 src 复制到 dest。
● 单调队列：https://blog.csdn.net/hnjzsyjyj/article/details/150471855
● AcWing 背包问题关系图

【算法代码】 

#include <bits/stdc++.h>
using namespace std;

const int N=2e4+5;
int f[N],pre[N];
int q[N]; //Monotonic queue to store indices

int main() {
    int n,V;
    cin>>n>>V;
    for(int i=1; i<=n; i++) {
        memcpy(pre,f,sizeof f); //copy f to pre
        int vol,val,cnt;
        cin>>vol>>val>>cnt;
        for(int j=0; j<vol; j++) {
            int hh=0,tt=-1;
            for(int k=j; k<=V; k+=vol) {
                /* 1.Queue's front exceeds the limit
                 of 【cnt items at most】, Pop out. */
                int max_limit=k-cnt*vol;
                if(hh<=tt && q[hh]<max_limit) {
                    hh++;
                }

                /* 2.Maintain the monotonic queue: queue's tail
                 is not as good as the current k, Pop out. */
                while(hh<=tt) {
                    int tt_idx=q[tt];
                    int val_tt=pre[tt_idx]-(tt_idx-j)/vol*val;
                    int val_now=pre[k]-(k-j)/vol*val;

                    if(val_tt<=val_now) tt--;
                    else break;
                }

                /* 3.Update the current f[k] with
                 the value of queue's front.*/
                if(hh<=tt) {
                    int best_idx=q[hh];
                    f[k]=max(f[k],pre[best_idx]+(k-best_idx)/vol*val);
                }

                /* 4.Push k into the queue.*/
                q[++tt]=k;
            }
        }
    }
    cout<<f[V]<<endl;

    return 0;
}

/*
in:
4 5
1 2 3
2 4 1
3 4 3
4 5 2

out:
10
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/126188992
https://blog.csdn.net/hnjzsyjyj/article/details/109363826
https://blog.csdn.net/hnjzsyjyj/article/details/126244362
https://www.acwing.com/solution/content/6500/

​