1 条题解

  • 0
    @ 2026-11-12 21:44:29

    [E] Knapsack 2(dp_e)题解

    题意简述

    同 Knapsack 1,但 W≤109W \le 10^9,而 vi≤103v_i \le 10^3、N≤100N \le 100。

    思路

    换个维度做 DP

    按重量做 DP 需要 O(W)O(W) 空间与时间,WW 高达 10910^9 不可行。但总价值 V=∑vi≤100×1000=105V = \sum v_i \le 100 \times 1000 = 10^5,很小。

    于是交换"维度的角色":设

    • gvg_v = 达到总价值恰好为 vv 时所需的最小总重量。

    转移(对每件 (w,v)(w, v),同样倒序枚举价值):

    gj=min⁡(gj,  gj−v+w).g_{j} = \min\left(g_j,\; g_{j-v} + w\right).

    最后答案是

    max⁡{ v:gv≤W }.\max\{\, v : g_v \le W \,\}.

    为什么正确

    gvg_v 精确刻画了"价值达到 vv 的最小代价(重量)"。若某个 vv 能以不超过 WW 的重量达成,那么它就是可行答案;在所有可行的 vv 中取最大。

    复杂度

    时间 O(N⋅∑vi)≤107O(N \cdot \sum v_i) \le 10^7,空间 O(∑vi)O(\sum v_i)。

    参考代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    long long g[100005];   // g[v] = 达到价值 v 的最小重量
    
    int main() {
        int n, W;
        scanf("%d %d", &n, &W);
        const long long INF = (1LL << 60);
        for (int v = 0; v <= 100000; v++) g[v] = INF;
        g[0] = 0;
        int V = 0;
        for (int i = 0; i < n; i++) {
            long long w; int v;
            scanf("%lld %d", &w, &v);
            for (int j = V + v; j >= v; j--)
                if (g[j - v] + w < g[j]) g[j] = g[j - v] + w;
            V += v;
        }
        int ans = 0;
        for (int v = 0; v <= V; v++)
            if (g[v] <= W) ans = v;
        printf("%d\n", ans);
        return 0;
    }
    

    易错点

    1. gvg_v 是"恰好等于 vv"的语义,初值必须是 INF,g0=0g_0 = 0;否则"不超过"的语义会让答案偏大。
    2. 求答案要枚举所有 vv 找满足 gv≤Wg_v \le W 的最大者,不能只看 gVg_V。
    3. 重量相加上限 10910^9 会超 int,w 与 gg 都用 long long。

    数据说明

    共 14 组:3 组官方样例;W=1W=1、单物品 w=Ww=W、全部 v=1v=1、全部 w=109w=10^9 边界;N=100N=100 随机(含 ww 接近 10910^9、uu 集中在 900–1000 的构造);专门放了"全部 w=109w=10^9 而 W=109W=10^9"的组,检验只看最小重量的实现是否正确。

    • 1

    信息

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