1 条题解

  • 0
    @ 2026-11-12 21:41:20

    [D] Knapsack 1(dp_d)题解

    题意简述

    NN 件物品,第 ii 件重量 wiw_i、价值 viv_i,背包容量 WW,每件最多取一次,求价值之和最大值。

    思路

    状态

    fjf_j = 当前已考虑的物品中,总重量恰好不超过 jj 时能获得的最大价值。

    转移

    对每件物品 (w,v)(w, v),倒序枚举 jj 从 WW 到 ww:

    fj=max⁡(fj,  fj−w+v).f_j = \max(f_j,\; f_{j-w} + v).

    倒序是关键:正序会让同一件物品被拿多次(那是完全背包)。倒序保证了 f[j-w] 还是"没考虑这件物品"的旧值。

    为什么正确

    这是 0/1 背包的标准做法:按物品顺序决策,fjf_j 始终表示"前 ii 件物品、容量 jj 的最优值",倒序遍历使得每件物品只被决策一次。

    复杂度

    时间 O(NW)≤107O(NW) \le 10^7,空间 O(W)O(W)。

    参考代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    long long f[100005];
    
    int main() {
        int n, W;
        scanf("%d %d", &n, &W);
        for (int i = 0; i < n; i++) {
            long long w, v;
            scanf("%lld %lld", &w, &v);
            for (int j = W; j >= w; j--)
                f[j] = max(f[j], f[j - (int)w] + v);
        }
        printf("%lld\n", f[W]);
        return 0;
    }
    

    易错点

    1. 必须倒序循环;正序会变成"物品可重复取"。
    2. 价值之和最大为 100×109=1011100 \times 10^9 = 10^{11},远超 int,样例 2 的答案就是 5×1095 \times 10^9,必须 long long。
    3. ff 初值全 00 即可(表示什么都不取)。

    数据说明

    共 16 组:3 组官方样例(含答案 5×1095\times10^9 的 64 位用例);N=1N=1、wi=Ww_i = W、全 w=1w=1、全 w=Ww=W 等边界;N=20/100N=20/100 随机;两组"全部 w=1w=1"与"全部 w=Ww=W"的构造组,专门检验倒序与容量边界。

    • 1

    信息

    ID
    13
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者