HIGH88 【模板】二维费用背包
题目描述
小红有 个事件可以分享。她希望在总耗时不超过
,总消耗精力不超过
的前提下,选择若干事件进行分享,使得收获的快乐值总和最大。
对于第 个事件,若要发布,需要耗费
分钟时间与
点精力,并能让她获得
点快乐值。每个事件最多只能选择一次。
解题思路
这是一个经典的二维费用背包问题。它本质上是一个0-1背包问题,但每个物品有两个不同的“费用”(或“体积”),这里分别是时间和精力。我们需要在这两个限制条件下,最大化总“价值”(快乐值)。
1. 状态定义
由于有两个费用维度,我们的动态规划状态也需要是二维的。
我们定义一个二维数组 ,
的含义是:在可用时间不超过
、可用精力不超过
的前提下,能获得的最大快乐值总和。
我们的最终目标就是求解
。
2. 状态转移方程
我们依次遍历每一个事件。对于第 个事件(耗时
,耗费精力
,快乐值
),当我们考虑更新状态
时,存在两种决策:
- 不选择事件
:这种情况下,最大快乐值保持不变,即为只考虑前
个事件时的
。
- 选择事件
:这个决策是可行的,当且仅当当前可用时间
且可用精力
。如果选择,那么我们需要在消耗掉
时间和
精力后的剩余资源(即
时间和
精力)所能达到的最大快乐值的基础上,加上事件
本身的快乐值。即
。
综合以上两种情况,我们取其中的较大者,得到状态转移方程:
3. 循环顺序(空间优化)
和标准的0-1背包问题一样,我们可以通过省去代表物品维度的第一维,将 数组的空间复杂度从三维优化到二维。为了确保每个事件只被选择一次(即防止在同一轮更新中重复使用事件
),我们必须逆序遍历两种费用(时间和精力)。
算法总结
- 初始化一个大小为
的二维
数组,所有元素为0。
- 外层循环遍历每个事件
(从 1 到
)。
- 中层循环逆序遍历时间
(从
到
)。
- 最内层循环逆序遍历精力
(从
到
)。
- 应用状态转移方程更新
。
- 所有循环结束后,最终答案为
。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Event {
int t, h, a;
};
int main() {
int n;
cin >> n;
int T, H;
cin >> T >> H;
vector<Event> events(n);
for (int i = 0; i < n; ++i) {
cin >> events[i].t >> events[i].h >> events[i].a;
}
vector<vector<long long>> dp(T + 1, vector<long long>(H + 1, 0));
for (int i = 0; i < n; ++i) {
int time_cost = events[i].t;
int energy_cost = events[i].h;
long long happiness = events[i].a;
// 逆序遍历确保每个事件只用一次
for (int j = T; j >= time_cost; --j) {
for (int k = H; k >= energy_cost; --k) {
dp[j][k] = max(dp[j][k], dp[j - time_cost][k - energy_cost] + happiness);
}
}
}
cout << dp[T][H] << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int T = sc.nextInt();
int H = sc.nextInt();
int[] t = new int[n];
int[] h = new int[n];
int[] a = new int[n];
for (int i = 0; i < n; i++) {
t[i] = sc.nextInt();
h[i] = sc.nextInt();
a[i] = sc.nextInt();
}
long[][] dp = new long[T + 1][H + 1];
for (int i = 0; i < n; i++) {
int timeCost = t[i];
int energyCost = h[i];
long happiness = a[i];
// 逆序遍历确保每个事件只用一次
for (int j = T; j >= timeCost; j--) {
for (int k = H; k >= energyCost; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - timeCost][k - energyCost] + happiness);
}
}
}
System.out.println(dp[T][H]);
}
}
def main():
n = int(input())
T, H = map(int, input().split())
events = []
for _ in range(n):
events.append(list(map(int, input().split())))
# 初始化dp数组
dp = [[0] * (H + 1) for _ in range(T + 1)]
for t, h, a in events:
# 逆序遍历确保每个事件只用一次
for j in range(T, t - 1, -1):
for k in range(H, h - 1, -1):
dp[j][k] = max(dp[j][k], dp[j - t][k - h] + a)
print(dp[T][H])
if __name__ == "__main__":
main()
算法及复杂度
- 算法: 二维费用背包 (动态规划)
- 时间复杂度:
,其中
是事件数量,
是时间上限,
是精力上限。我们需要三层循环来填充
表。
- 空间复杂度:
,需要
的空间存储
个事件的输入数据,以及
的空间来存储
数组。