题目描述

1. 多重背包问题 III

C++ 代码

/*
题解：
对于一种物品而言，存在v种情况。假设前面已经选择了1、2、3 …… v
对同一种情况来说，它是一个等差数列，公差是v。
f[j] : 对于余数为j的情况。f[j] = max(f[j-v]+w,f[j-2*v]+2*w ..... f[j-k*v]+k*w);

（此处的0、v、2v表示的是背包剩余的体积。在同种物品的情况下，剩余的体积越小，其价值越大。
但是记录的时候是相反的，也就是说f[j]记录下来的是背包存在体积为j的物品时，所拥有价值）
f[0] 
f[v] - 1 * w
f[2v] - 2 * w
....
f[kv] - k * w  :在余数为0里面的第k个数

f[i]只与f[i-1]有关，因此多声明一个数组来存前一个的情况
*/
#include <bits/stdc++.h>
using namespace std;

const int MAX =20007;
int f[MAX];
int p[MAX];//由于f数组的计算公式是 max(f[i-1][j],f[i-1][j-v],...)，p存储的是前一个状态（i-1）的值
int q[MAX];

int N,V;

int main(){
    cin>>N>>V;
    for(int i = 1;i<=N;++i){
        memcpy(p,f,sizeof(f));
        int v,w,s;
        cin>>v>>w>>s;
        for(int j = 0;j<v;++j){         //取余，分组。
            int tail = -1,head=0;
            for(int k = j;k<=V;k+=v){   //遍历组内情况

                if(head<=tail && k-s*v>q[head])head++;
                //当其超出使用次数时，由于是单调递增数列，所以后面的一定比前面的值要大，出队列。
                //**限制队列长度**

                if(head<=tail)f[k]=max(f[k],p[q[head]]+(k-q[head])/v*w);

                //比较当前状态的最大值，**这里就是为什么后面队列尾部元素要减k*w的原因。**
                //（因为你放到余数为j的第k个数是队列里面最大的数+新增(k-q[head])/v个物品后的价值）

                while(head<=tail && p[q[tail]]-(q[tail]-j)/v*w <=p[k]-(k-j)/v*w)tail--;
                //看上面解释

                q[++tail]=k;
            }
        }
    }
    cout<<f[V]<<endl;
    return 0;
}

参考文献

yxc大神的讲解