题目描述

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

第 i 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。

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

输入格式

第一行两个整数，\(N,V (0<N≤1000, 0<V≤20000)\)，用空格隔开，分别表示物品种数和背包容积。

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

输出格式

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

数据范围

\(0<N≤1000\)
\(0<V≤20000\)
\(0<v_i,w_i,s_i≤20000\)

提示

本题考查多重背包的单调队列优化方法。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

算法思路

从最简单的多重背包讲起，代码如下

cin >> n >> m;

for(int i = 1; i <= n; i++)
  	cin >> v >> w >> s;
  	for(int j = 1; j <= m; j++)
      	for(int k = 0; k <= s && k * v <= j; k++)
          dp[i][j] = max(dp[i][j], dp[i-1][j-k*v]+k*w);
cout << dp[n][m];

我们将体积j换一种表达方式写出进行观察

0*v, 0*v+1, 0*v+2, ..., 0*v+v-1, 1*v+0, 1*v+2, ..., k*v+t		 (0 <= t < v)
这里k*v+t == j

可以发现，当更新dp[i][j]时，只需要用到j mod v相同的dp元素

\(比如当j = t*v + 3 (0\le t \le k)时\)

\(dp[j] = max(dp[t*v+3], dp[(t-1)*v+3],dp[(t-2)*v+3],...,dp[3])\)

因此在对dp[i][j]进行更新时，可以按照mod v的值将其分类，

根据j % v = 0、1、 2、......、v - 1分成v类，按照类进行更新

按照类更新，我们可以引入单调队列，减少寻找max的花费

假设当前j = t *v + 3，我们的更新顺序就是dp[3], dp[3*2]，dp[3*3], .....我们将每个结果存储到单调队列中

因为\(dp[j] = dp[t*v + 3] = max(dp[t*v + 3],dp[(t-1)*v+3],dp[(t-2)*v+3],...)\)

因此在更新dp[j]时，只需要将dp[j]入队，此时单调队列的队头即为max结果

Q1、处理w的变化问题

假设j = 2 * v + 3

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

而当j = 3 * v + 3时

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

可以看出当j不同时，dp[3]后边的w不断的在变化，因此之前更新dp[3]时放入的值，在后续更新时是无效的，因此我们换一种表达方法÷

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
...
这样，每次入队的值是 dp[j+k*v] - k*w, 出队时加上对应的w即可

Q2、单调队列长度是多少？什么时候需要出队？

注意多重背包是有个数限制的，观察转移方程，假设体积j足够大，那么

\(dp[i][j] = max(dp[i-1][j], dp[j-v]+w,dp[j-2v]+2w,...dp[j-sv]+sw)\)

观察可知，点j处的值，只和[j-s*v, j]内的元素有关,因此

• 单调队列长度是s*v

• 当队头元素的位置小于( j-s*v )时，就应该出队

实现

#include<iostream>
#include<cstring>

using namespace std;

const int N = 20010;

int n, m;
int v, w, s;
int p[N], dp[N], pre[N];

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> v >> w >> s;
        memcpy(pre, dp, sizeof dp);
        for(int j = 0; j < v; j++){
            int hh = 0, tt = -1;
            for(int k = j; k <= m; k+=v){
                //1.看要不要出队
                if(hh <= tt && p[hh] < k - s * v) ++hh;
                //2.找到位置
                while(hh <= tt && pre[p[tt]] - (p[tt] - j) / v * w <= pre[k] - (k - j) / v * w) --tt;
                //3.入队
                p[++tt] = k;
                //4.更新dp
                dp[k] = pre[p[hh]] + (k - p[hh]) / v * w;
            }
        }
    }
    cout << dp[m];
}