首页 > 试题广场 >

【模板】二维费用背包

[编程题]【模板】二维费用背包

热度指数：664 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 小红非常喜欢在社交平台分享生活点滴。她的生活中共有 $n$ 个事件，第 $i$ 个事件若要发布，需要耗费 $t_i$ 分钟时间与 $h_i$ 点精力，并能让她获得 $a_i$ 点快乐值。

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

输入描述:

第一行输入一个整数 ——事件数量。

第二行输入两个整数 ——可用时间与可用精力上限。

接下来  行，第  行输入三个整数 ，描述第  个事件的参数。

输出描述:

输出一个整数，代表在限制条件内能获得的最大快乐值。

示例1

输入

输出

说明

选择事件  与事件 ：耗时 ，耗费精力 ，快乐值 。

示例2

输入

输出

说明

任何单个事件都超过精力或时间限制，小红只能选择不分享，快乐值为 。

算法知识视频讲解

Python3

卡卡喵

暴力循环来了

import sys

data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it))
T = int(next(it))
H = int(next(it))
event = [[0, 0, 0]]
for _ in range(n):
    t = int(next(it))
    h = int(next(it))
    a = int(next(it))
    if t <= T and h <= H:
        event.append([t, h, a])

dp = [[[0 for _ in range(T + 1)] for _ in range(H + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    item = event[i]
    for j in range(H + 1):
        for k in range(T + 1):
            if k >= item[0] and j >= item[1]:
                dp[i][j][k] = max(
                    dp[i - 1][j][k], dp[i - 1][j - item[1]][k - item[0]] + item[2]
                )
            else:
                dp[i][j][k] = dp[i - 1][j][k]

print(dp[-1][-1][-1])

发表于今天 00:14:05 回复(0)