首页 > 试题广场 >

【模板】二维费用背包

[编程题]【模板】二维费用背包
  • 热度指数：490 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
\hspace{15pt}小红非常喜欢在社交平台分享生活点滴。她的生活中共有 n 个事件，第 i 个事件若要发布，需要耗费 t_i 分钟时间与 h_i 点精力，并能让她获得 a_i 点快乐值。

\hspace{15pt}在本次挑战中，小红希望在总耗时不超过 T，总消耗精力不超过 H 的前提下，选择若干事件进行分享，使得收获的快乐值总和最大。请你帮她计算她最多能获得多少快乐值。

输入描述:
\hspace{15pt}第一行输入一个整数 n\ (1\leqq n\leqq50)——事件数量。

\hspace{15pt}第二行输入两个整数 T,H\ (1\leqq T,H\leqq500)——可用时间与可用精力上限。

\hspace{15pt}接下来 n 行，第 i 行输入三个整数 t_i,h_i,a_i\ \bigl(1\leqq t_i,h_i\leqq30,\ 1\leqq a_i\leqq10^9\bigr)，描述第 i 个事件的参数。


输出描述:
\hspace{15pt}输出一个整数，代表在限制条件内能获得的最大快乐值。
示例1

输入

3
5 4
1 2 2
2 1 3
4 1 5

输出

7

说明

选择事件 1 与事件 3：耗时 1+4=5\leqq T，耗费精力 2+1=3\leqq H，快乐值 2+5=7。
示例2

输入

2
2 2
1 3 3
3 1 4

输出

0

说明

任何单个事件都超过精力或时间限制，小红只能选择不分享，快乐值为 0。
算法知识视频讲解
开通博客
头像 lhz666
发表于 2025-07-24 09:40:28
假设题目没有T这个约束，则这道题目可以看做 01 背包模板问题，所以我们只需要在 01 背包的基础上添加一层循环用来表示 T 的约束就可以了，dp[t][h] 表示在耗费t分钟和h点精力的情况下所收获的最大快乐值。 #include <bits/stdc++.h> using names 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 冷艳的西红柿刷牛客
发表于 2025-11-20 19:58:49
#include <iostream> #include <vector> #include <cstring> using namespace std; //相比一维多了一次循环一个状态，状态压缩还是和一维差不多，核心是确保本轮不会访问到已经更新的值，这个显 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-01 12:22:33
HIGH88 【模板】二维费用背包 题目描述 小红有 个事件可以分享。她希望在总耗时不超过 ，总消耗精力不超过 的前提下，选择若干事件进行分享，使得收获的快乐值总和最大。 对于第 个事件，若要发布，需要耗费 分钟时间与 点精力，并能让她获得 点快乐值。每个事件最多只能选择一次。 解题思 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Silencer76
发表于 2025-08-22 00:20:02
题目链接 【模板】二维费用背包 题目描述 小红有 个事件可以分享。对于第 个事件，分享需要花费 分钟时间和 点精力，并能获得 点快乐值。小红希望在总耗时不超过 ，总消耗精力不超过 的前提下，选择分享若干事件，使得获得的快乐值总和最大。 输入: 第一行输入一个整数 ，表示事件数量。 第二 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 小胡放轻松
发表于 2025-11-23 00:13:28
/*我遇到的动态规划问题不多，只能先利用0,1背包问题的初级解法来看，设置dp[n + 1][T + 1][H + 1]数组，三个维度上有一维是0则整体的值为0，这在初始化时候要做到，之后就是为数组赋值了，这里用到3层循环 dp数组的赋值逻辑是：if(event[i - 1][0] <= j 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 小红书
难度：
0条回答 47浏览

热门推荐

相关试题

【模板】二维费用背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号