算法

对于每个物品i 对应体积vi 数量si 价值 wi
已知原暴力解法：
for(int j=0; j<=m; j){
f[i][j] = f[i-1][j];
for(int k=1; k<=si&&k*vi<=j; k)
f[i][j] = Math.max(f[i][j], f[i-1][j-kvi]+kwi);

}
当前物品体积vi, 暴力做法 要枚举每一个体积j下的max, 通过观察
f[i][j] = Math.max(f[i][j],f[i-1][j-kvi]+kwi)可以知道 每一此更新 均是来自 j-k*vi 中 所以更确切的说 j mod vi 模值相同的j中 各个模值对应的v的集合都是相互独立的 不相交的 例如
当前 j = 15, vi = 3 则可以将j 分为三组 {3， 6， 9， 12， 15} {1， 4， 7， 10， 13} {2， 5， 8， 11， 14}
f[i-1][j] 的更新 只会从j % vi ~ j 中的 价值最大 这点很重要 这样我们就不用 每个j都从头找最大值了 一组一组更新（因为都是相互不影响的） 最后这个f 就被更新了

(单调队列)

在遍历每个组中体积时 需要考虑每个元素当前si的最大值 这里用单调队列实现 具体看代码

需要注意的是 单调队列中存的是 体积k 在将当前值插入队列 或 从队列中取出值时
f[i-1][j] = max{f[i-1][j],f[i-1][j-vi]+w, f[i-1][j-2vi]+2w,......}
f[i-1][j+v] = max{f[i-1][j+vi],f[i-1][j]+w, f[i-1][j-vi]+2w,......}
在与队列中元素比较时 从队列首段取出元素 对应的价值g[q[tt]]+(k-q[tt])/viwi（具体看代码）

时间复杂度

参考文献

Java 代码

static final int N = 1010;
static int[]f, g, q;//分别存储 f[i][j]、f[i-1][j]、queue

public static void main(String[] args) throws Exception{
    int n, m;
    n = nextInt(); m = nextInt();
    f = new int[m+1];
    g = new int[m+1];
    q = new int[m+1];

    int vi, wi, si;
    for(int i=1; i<=n; i++){
        vi = nextInt(); wi = nextInt(); si = nextInt();
        for(int j=0; j<vi; j++){
            int hh, tt;
            hh = 0; tt = -1;
            for(int k=j; k<=m; k+=vi){
                g[k] = f[k];//每次f[k]都可能会更新， 预先保存f[i-1, k]的值 
                if(hh<=tt&&(k-q[hh])/vi>si) hh++;//保证保证不超前si个
                while(hh<=tt&&g[q[tt]]+(k-q[tt])/vi*wi <f[k]) tt--;//单调队列入队方法
                q[++tt] = k;
                f[k] = g[q[hh]]+(k-q[hh])/vi*wi;
            }

        }

    }