Oiclass P1255 题解

又是一个我背不动的背包

这次是 0/1 背包 plus——多重背包，下面是经典的五步

1. 划分阶段

以每一个物品为一个阶段，表示这个物品前的物品的最大值（包括这个物品自身）。

2. 确定状态和状态变量

搞一个一维数组 \(f\) ，即 \(f_i\) 表示第 \(1\) 个物品到第 \(i\) 个物品之间（算头算尾）的最优解，也就是在空间不超过 \(v\) 的情况下最大的价值总和。

3. 确定决策并写出状态转移方程

决策方式不算复杂，对于一个状态 \(f_i\) 他可以有以下两种取值方式： \[ \left\{ \begin{array}{lr} f_{i}=f_{i-1}\\ f_i=f_{i-w_i}+v_i \end{array} \right. \] 对于这两种取值的方式，调大的就行，不用考虑太多，简化一下就是这样： \[ f_i=\max(f_{i-1},\ f_{i-w_i}+v_i) \]

4. 边界条件

对于几乎所有背包，所有边界条件都是没有边界条件，也就是边界条件为 \(0\) 。这道题目也不例外

5. 实现

直接模拟，记得第二层循环要倒序

#include<iostream>

using namespace std;

int n, v, W, S, M, total, w[20009], s[20009], f[2009];

int main() {
    cin >> n >> v;
    for (int i = 1; i <= n; i++) {
        cin >> M >> W >> S;
        M = min(M, v / W);
        for (int j = 1; j <= M; j <<= 1) {
            w[++total] = W * j;
            s[total] = S * j;
            M -= j;
        }
        if (M > 0) {
            w[++total] = W * M;
            s[total] = S * M;
        }
    }
    for (int i = 1; i <= total; i++) {
        for (int j = v; j >= w[i]; j--) {
            f[j] = max(f[j], f[j - w[i]] + s[i]);
        }
    }
    cout << f[v];
}