题目描述

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

题解

首先回顾0-1背包问题的dp方程：

dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - v] + w)

而在本题中，同一个物品最多可以取s次，那么dp方程可以由0-1背包方程改造：

dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - v] + w , dp[i - 1][j - 2 * v] + 2 * w , ..... , dp[i - 1][j - s * v] + s * w) //假设j - s * v > 0)

滚动数组优化后，得：

dp[j] = max(dp[j] , dp[j - v] + w , dp[j - 2 * v] + 2 * w , ..... , dp[j - s * v] + s * w) //假设j - s * v > 0)

那么有问题就转化成求dp[j] , dp[j - v] + w , dp[j - 2 * v] + 2 * w , ..... , dp[j - s * v] + s * w)的最大值，对于每一个dp数组的值，都需要求一遍最大值，显然时间复杂度不可接受，于是本题的核心就是对求最大值的方式进行优化。

优化

观察dp方程，

dp[j] = max(dp[j] , dp[j - v] + w , dp[j - 2 * v] + 2 * w , ..... , dp[j - s * v] + s * w) //假设j - s * v > 0)

可知，j只和前面间隔v的dp数组相关，也就是说j、j - v、 j - 2v … j - sv都是同余的，我们将同余的归为一组，而dp[0…V]中共有v组。既然如此，可以对dp方程稍作修改，令j范围是(0 < j < v)，j就意味着同余的余数。则dp方程为：

dp[j]    =     dp[j]
dp[j+v]  = max(dp[j] +  w,  dp[j+v])
dp[j+2v] = max(dp[j] + 2w,  dp[j+v] +  w, dp[j+2v])
dp[j+3v] = max(dp[j] + 3w,  dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])
.....

对上述方程稍作修改，变为如下形式：

dp[j]    =     dp[j]
dp[j+v]  = max(dp[j], dp[j+v] - w) + w
dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w
dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w
......

这样，每个max函数内的形式就统一了，形式统一的好处就是dp[j + 2v]就是前2项的最大值，当求第三项时，不需要全局比较，只需要和第二项比较即可。此时对求dp[j],dp[j + v],dp[j + 2v],…,,dp[j + sv]维护一个单调队列，由于单调队列队首始终存放最大值，当计算dp[j +kv]时，只需要比较dp[j +(k - 1)v] - (k - 1)w 和 dp[j + kv] - kw即可。因为dp[j +(k - 1)v] - (k - 1)w 已经是前k - 1项最大值了。

代码

int[] dp = new int[10010]; // dp数组
int[] que = new int[10010]; // 单调队列，存储dp[j + kv]中的k值
for(int i = 0; i < N; i++){ // 外层循环遍历物品
    for(int r = 0; r < v; r++){ // 遍历余数，余数r 0 < r < v
        int head = 0, tail = -1;
        for(int k = 0; r + k * v < m; k++){ // 和r所有同余的dp数组元素即 dp[r] , dp[r + 1v] , dp[r + 2v]....
            /*
            由于同余的数组元素数量可能超过同一物品的使用次数s。
            k - que[head] > s 实际为 ((r + k * v) - (r + que[head] * v)) / v > s ，((r + k * v)当前遍历到的数组元素下标，(r + que[head] *             v))当前遍历到下标之前的最大数组元素的下标。
            */
            if(head <= tail && k - que[head] > s) head++; // 超过s时，队首出队。
            // 比较当前数组元素和单调队尾相比，当前元素大则删除队尾原有元素。使得队列单调递减。
            while(head <= tail && dp[r + k * v] - k * w >= dp[r + que[tail] * v] - que[tail] * w) tail--;
            // 插入k值到队列
            que[++tail] = k;
            // 以上的步骤就是更新单调队列并使队首为全局最大，
            // 更新当前dp数组
            dp[r + k * v] = dp[r + que[head] * v] - que[head] * w + k * w;
        }
    }
}
return dp[V];