竞极 Ace

二维费用背包

二维费用背包

一、问题描述

有 nn 件物品，第 ii 件物品的重量为 w[i]w[i]，体积为 c[i]c[i]，价值为 v[i]v[i]，每件物品最多选择一次。

背包的重量上限为 WW，体积上限为 CC。求总重量不超过 WW、总体积不超过 CC 时，能够得到的最大总价值。

与普通 01 背包相比，只是增加了一种资源限制，因此也称为二维费用的 01 背包。这里的“二维”指两种费用，而不是 DP 数组的维数。

二、状态与转移

设 dp[i][j][k]dp[i][j][k] 表示：只考虑前 ii 件物品，重量不超过 jj、体积不超过 kk 时的最大总价值。

仍然枚举第 ii 件物品选或不选：

$$dp[i][j][k]=\max\left( dp[i-1][j][k],\quad dp[i-1][j-w[i]][k-c[i]]+v[i] \right).$$

第二项要求 j≥w[i]j\ge w[i] 且 k≥c[i]k\ge c[i]，否则只能不选。

允许不选任何物品，因此 dp[0][j][k]=0dp[0][j][k]=0。答案为 dp[n][W][C]dp[n][W][C]。

三、压缩物品维度

省去第一维，使用 dp[j][k] 保存状态，转移为：

dp[j][k] = max(dp[j][k], dp[j - w][k - c] + v);

两个容量统一倒序枚举。 这样转移来源仍保存上一轮的状态，保证当前物品最多选择一次。

输入第一行为 n,W,Cn,W,C，接下来 nn 行，每行输入一件物品的重量、体积和价值。输出最大总价值。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, W, C;
    cin >> n >> W >> C;
    vector<vector<long long>> dp(W + 1, vector<long long>(C + 1, 0));

    for (int i = 1; i <= n; ++i) {
        int w, c;
        long long v;
        cin >> w >> c >> v;

        for (int j = W; j >= w; --j) {
            for (int k = C; k >= c; --k) {
                dp[j][k] = max(dp[j][k], dp[j - w][k - c] + v);
            }
        }
    }

    cout << dp[W][C] << '\n';
    return 0;
}

时间复杂度为 O(n(W+1)(C+1))O(n(W+1)(C+1))，空间复杂度为 O((W+1)(C+1))O((W+1)(C+1))，容量为正时通常简写为 O(nWC)O(nWC) 和 O(WC)O(WC)。