01 背包习题题解（洛谷题单）

本篇对应源码见仓库 solutions/xcpc/algorithm/dp/knapsack-01/。

题单

P1048 采药

题意

这是01背包的基础模拟题。

思路

模板题

示例代码

signed main() {
    IOS;

    int T, M;
    cin >> T >> M;
    vector<int> Weight(M + 1), Val(M + 1);
    fer(i, 1, M + 1) cin >> Weight[i] >> Val[i];

    // dp[i] : 时间i内的最大价值
    vector<int> dp(T + 1);
    fer(i, 1, M + 1) {
    	ferd(t, T, Weight[i]) {
    		dp[t] = max(dp[t], dp[t - Weight[i]] + Val[i]);
    	}
    }
    cout << dp[T] << '\n';
    return 0;
}

P1049 装箱问题

题意

这是稍作变化的01背包基础题。物品的价值 = 其对应的体积。

思路

体积覆盖价值，模板题。

示例代码

signed main() {
    IOS;

    int V, n;
    cin >> V >> n;
    vector<int> v(n + 1);
    fer(i, 1, n + 1) cin >> v[i];

    // dp[v]:容量为v的最大价值
    vector<int> dp(V + 1);
    fer(i, 1, n + 1) {
    	ferd(j, V, v[i]) {
    		dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
    	}
    }
    cout << V - dp[V] << '\n';
    return 0;
}

P1164 小A点菜

题意

这是01背包中恰好装满问题，并且是询问方案总数。关于做法的分析与拓展具体请参见恰好装满的 tutorial 与 01 背包 tutorial

思路

只是状态转移方程与 $dp$ 数组初始化发生变化。

示例代码

signed main() {
    IOS;

    int n, M;
    cin >> n >> M;
    vector<int> arr(n + 1);
    fer(i, 1, n + 1) cin >> arr[i];

 	// dp[m]:刚好花完m的方案数
    vector<int> dp(M + 1);
    dp[0] = 1;

    fer(i, 1, n + 1) {
    	ferd(j, M, arr[i]) {
            dp[j] = dp[j] + dp[j - arr[i]];
    	}
    }
    cout << dp[M] << '\n';

    return 0;
}

P1060 开心的金明

题意

物品的价值发生变化，还是一道板子题。

思路

重新定义价值，模板题。

示例代码

signed main() {
    IOS;

    int n, m;
    cin >> n >> m;
    vector<int> Weight(m + 1), Val(m + 1);

    fer(i, 1, m + 1) {
    	int v, p;
    	cin >> v >> p;
    	Weight[i] = v;
    	Val[i] = v * p;
    }

    vector<int> dp(n + 1);
    fer(i, 1, m + 1) {
    	ferd(j, n, Weight[i]) {
    		dp[j] = max(dp[j], dp[j - Weight[i]] + Val[i]);
    	}
    }
    cout << dp[n] << '\n';

    return 0;
}

P3985 不开心的金明

题意

背包容量很大(1e9)，并且对物品的选择有限制，01背包加强题。

思路

• 题目所给出的物品的重量的极差不超过3，也就是说重量最多只有4中状态。
• 将不同状态的物品划为一组
• 同一组里肯定是优先选择价值更高的，因此对每组按价值降序排列。
• $N$ 最大是100, 可以直接枚举每一组选择的个数（计算价值可以前缀和预处理），肯定不会$TLE$

示例代码

signed main() {
    IOS;

    int n;
    ll W;
    cin >> n >> W;

    vector<ll> v(n), p(n);
    ll b = inf;
    fer(i, 0, n) {
        cin >> v[i] >> p[i];
        b = min(b, v[i]);
    }

    // 四组：d = v[i] - b ∈ {0,1,2,3}
    vector<ll> groups[4];
    fer(i, 0, n) {
        int d = int(v[i] - b);
        groups[d].push_back(p[i]);
    }

    // 对每组排序并做前缀和
    vector<vector<ll>> S(4);
    fer(d, 0, 4) {
        auto &G = groups[d];
        sort(G.rbegin(), G.rend());  // 降序
        S[d].assign(G.size() + 1, 0);
        fer(k, 1, G.size() + 1) {
            S[d][k] = S[d][k - 1] + G[k - 1];
        }
    }

    // 四重枚举
    ll ans = 0;
    ll c[4] = { b, b+1, b+2, b+3 };
    fer(k0, 0, groups[0].size() + 1) {
        fer(k1, 0, groups[1].size() + 1) {
            fer(k2, 0, groups[2].size() + 1) {
                fer(k3, 0, groups[3].size() + 1) {
                    ll cost = k0*c[0] + k1*c[1] + k2*c[2] + k3*c[3];
                    if(cost > W) continue;
                    ll val = S[0][k0] + S[1][k1] + S[2][k2] + S[3][k3];
                    ans = max(ans, val);
                }
            }
        }
    }

    cout << ans << "\n";

    return 0;
}