题解 | 【模板】01背包

#include <iostream>
using namespace std;

// 新增：定义负无穷（表示「无法装满」的非法状态）
const int INF = 0x3f3f3f3f;

struct it {
    int v = 0;
    int w = 0;
};
const int N = 1e3 + 5;
it a[N];
int f[N][N];  // 保留原变量名，先算res1，再重置算res2

int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].v >> a[i].w;
    }

    /*
    考虑「第 i 个物品、第 i+1 个物品、…、第 n 个物品」这部分物品时，恰好装满体积 j 的最大价值。
    举个例子：
    若 n=3（3 个物品），则：
    f[3][j]：只考虑第 3 个物品时，恰好装满 j 的价值；
    f[2][j]：考虑第 2、3 个物品时，恰好装满 j 的价值；
    f[1][j]：考虑第 1、2、3 个物品（所有物品）时，恰好装满 j 的价值。
    */

    // ========== 第一部分：计算res1（不要求装满，原逻辑不变） ==========
    //不在意是否装满，只保证物品体积不溢出背包容量
    int res1 = 0;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= V; j++) {
            if (j < a[i].v) {
                f[i][j] = f[i + 1][j];
            } else f[i][j] = max(f[i + 1][j], f[i + 1][j - a[i].v] + a[i].w);
            res1 = max(f[i][j], res1);
        }
    }
    // ========== 第二部分：计算res2（恰好装满，重新初始化+状态转移） ==========
    // 关键1：重置f数组，初始化「没有物品时（i=n+1）」的状态
    // f[n+1][0] = 0（体积0恰好装满，合法）；f[n+1][1~V] = -INF（非法）
    for (int j = 0; j <= V; j++) {
        //设置条件，保证没装满就是非法条件
        if (j == 0) f[n + 1][j] = 0;   
        else f[n + 1][j] = -INF;
    }

    // 关键2：用「恰好装满」的逻辑重新计算f数组（遍历逻辑和原代码一致）
    int res2 = 0;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= V; j++) {
            if (j < a[i].v) {
                // 装不下当前物品，继承考虑i+1件物品时的状态（如果该容量在i+1件物品时是非法时，此时也非法）
                f[i][j] = f[i + 1][j];
            } else {
                // 装得下时，只选「合法状态」的最大值（避免把非法状态当0算）
                f[i][j] = max(f[i + 1][j], f[i + 1][j - a[i].v] + a[i].w);
            }
        }
    }

    // 关键3：最终判断f[1][V]是否合法（不是负无穷才是有效答案）
    if (f[1][V] > 0) res2 = f[1][V];
    else res2 = 0;  // 无法恰好装满，价值为0

    // 输出结果
    cout << res1 << endl;
    cout << res2 << endl;

    return 0;
}