【模板】二维费用背包

[题目链接](https://www.nowcoder.com/practice/84b88177894c4c82980017e6b4a15fb3)

思路

本题是经典的二维费用背包问题。有 个事件，每个事件有两种费用（时间 和精力 ）以及一个价值（快乐值 ）。需要在总时间不超过 、总精力不超过 的前提下，选择若干事件使快乐值总和最大。

状态定义

设 表示可用时间恰好为 、可用精力恰好为 时能获得的最大快乐值。

状态转移

对每个事件 （时间 ，精力 ，快乐值 ），逆序枚举两个维度：

$$

其中 从 到 ， 从 到 。逆序枚举保证每个事件最多被选一次（0-1 背包的经典技巧）。

为什么是二维而不是一维？

相比普通 0-1 背包只有一种容量限制，这里同时有时间和精力两种限制，因此 DP 数组需要两个维度分别追踪两种资源的消耗。

注意事项

  • 快乐值 可达 量级，多个事件累加后会超过 int 范围，DP 数组和相关变量必须使用 64 位整数（long long / long）。

样例演示

以示例 1 为例：，，，三个事件分别为 、、。

选择事件 1 和事件 3：时间 ，精力 ，快乐值 ，这是最优方案。

复杂度

  • 时间复杂度：，三重循环。
  • 空间复杂度：，使用滚动数组优化后只需一个二维 DP 数组。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int T, H;
    cin >> T >> H;
    vector<vector<long long>> dp(T+1, vector<long long>(H+1, 0));
    for(int i = 0; i < n; i++){
        int t, h;
        long long v;
        cin >> t >> h >> v;
        for(int j = T; j >= t; j--){
            for(int k = H; k >= h; k--){
                dp[j][k] = max(dp[j][k], dp[j-t][k-h] + v);
            }
        }
    }
    cout << dp[T][H] << "\n";
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int T = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        long[][] dp = new long[T + 1][H + 1];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int t = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            long v = Long.parseLong(st.nextToken());
            for (int j = T; j >= t; j--) {
                for (int k = H; k >= h; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - t][k - h] + v);
                }
            }
        }
        System.out.println(dp[T][H]);
    }
}