刷题记录 414.小U生活事件快乐值最大化414.小U生活事件快乐值最大化 问题描述 小U喜欢分享她的日常生活。她有n个

做自己喜欢的事：无论大小，做自己喜欢的事情，就是最大的快乐源泉。 #生活乐趣# #日常生活趣事# #简单快乐的生活哲学# #简单快乐的哲理故事#

文章讨论小U分享生活事件以最大化快乐值的问题，这是个0/1背包问题。给定n个事件，每个事件有时间、精力消耗和快乐值，在总时间不超T、总精力不超H的限制下求最大快乐值。采用DP解决，定义三维dp数组，给出递推关系和初始条件，用Python实现代码，分析了复杂度，并提出空间优化方法。

关联问题: 如何优化算法效率 DP数组能再简化吗 还有其他解法吗

414.小U生活事件快乐值最大化

问题描述

小U喜欢分享她的日常生活。她有n个事件可以选择分享，分享第ii个事件需要花费ti的时间和hi的精力来编辑文章，并能够获得ai的快乐值。小U想知道，在总花费时间不超过T且总花费精力不超过H的前提下，她最多可以获得多少快乐值。

测试样例

样例1：

输入：n = 2 ,T = 2 ,H = 2 ,t = [1, 3] ,h = [3, 1] ,a = [3, 4]
输出：0

样例2：

输入：n = 3 ,T = 5 ,H = 5 ,t = [2, 1, 3] ,h = [1, 3, 2] ,a = [10, 7, 8]
输出：18

样例3：

输入：n = 1 ,T = 3 ,H = 3 ,t = [4] ,h = [4] ,a = [5]
输出：0

思路

可以看作是0/1背包问题，要在给定的时间和精力限制下，选择一组事件让总的快乐值最大化。每个事件只能选择一次，选择某个事件会消耗一定的时间和精力，并带来一定的快乐值。使用dp解决问题，义一个三维的 dp 数组来表示在给定的时间和精力限制下，能达到的最大快乐值：

dp[i][j][k] 表示在前 i 个事件中，时间限制为 j，精力限制为 k 时，能够获得的最大快乐值。

递推关系：

不选择第 i 个事件：dp[i][j][k] = dp[i-1][j][k] 选择第 i 个事件（如果 j >= t[i] 且 k >= h[i]）：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j - t[i]][k - h[i]] + a[i])

初始条件：

dp[0][j][k] = 0，即没有事件时，最大快乐值为 0。

代码实现

def solution(n: int, T: int, H: int, t: list, h: list, a: list) -> int: # 初始化三维 DP 数组，大小为 (n+1) x (T+1) x (H+1) dp = [[[0] * (H + 1) for _ in range(T + 1)] for _ in range(n + 1)] # 遍历每个事件 for i in range(1, n + 1): time_required = t[i - 1] # 第 i 个事件的时间需求 energy_required = h[i - 1] # 第 i 个事件的精力需求 happiness = a[i - 1] # 第 i 个事件的快乐值 # 遍历所有可能的时间和精力组合 for j in range(T + 1): for k in range(H + 1): # 不选择第 i 个事件 dp[i][j][k] = dp[i - 1][j][k] # 选择第 i 个事件，如果满足时间和精力的限制 if j >= time_required and k >= energy_required: dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - time_required][k - energy_required] + happiness) # 返回最大快乐值，考虑所有事件和时间精力限制 return dp[n][T][H]

问题描述
小U喜欢分享她的日常生活。她有
n
n个事件可以选择分享，分享第
i
i个事件需要花费
t
i
t
i
​
的时间和
h
i
h
i
​
的精力来编辑文章，并能够获得
a
i
a
i
​
的快乐值。小U想知道，在总花费时间不超过
T
T且总花费精力不超过
H
H的前提下，她最多可以获得多少快乐值。

测试样例
样例1：

输入：n = 2 ,T = 2 ,H = 2 ,t = [1, 3] ,h = [3, 1] ,a = [3, 4]
输出：0

样例2：

输入：n = 3 ,T = 5 ,H = 5 ,t = [2, 1, 3] ,h = [1, 3, 2] ,a = [10, 7, 8]
输出：18

样例3：

输入：n = 1 ,T = 3 ,H = 3 ,t = [4] ,h = [4] ,a = [5]
输出：0 py解决

2024/11/30 01:05:16

重试

删除

固定

复制

下载为word文档

播放

这个问题可以看作是一个 0/1 背包问题。我们需要在给定的时间和精力限制下，选择一组事件，使得总的快乐值最大化。每个事件只能选择一次，选择某个事件会消耗一定的时间和精力，并带来一定的快乐值。

问题分析：

输入：

n：事件的数量。 T：可用的总时间。 H：可用的总精力。 t[i]：第 i 个事件所需的时间。 h[i]：第 i 个事件所需的精力。 a[i]：第 i 个事件带来的快乐值。

输出：

在时间和精力的限制下，能获得的最大快乐值。 思路：

我们可以用动态规划（DP）来解决这个问题。定义一个三维的 dp 数组来表示在给定的时间和精力限制下，能达到的最大快乐值：

dp[i][j][k] 表示在前 i 个事件中，时间限制为 j，精力限制为 k 时，能够获得的最大快乐值。

递推关系：

不选择第 i 个事件：dp[i][j][k] = dp[i-1][j][k] 选择第 i 个事件（如果 j >= t[i] 且 k >= h[i]）：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j - t[i]][k - h[i]] + a[i])

初始条件：

dp[0][j][k] = 0，即没有事件时，最大快乐值为 0。 Python 代码实现：

def max_happiness(n, T, H, t, h, a): # 初始化三维 DP 数组，大小为 (n+1) x (T+1) x (H+1) dp = [[[0] * (H + 1) for _ in range(T + 1)] for _ in range(n + 1)] # 遍历每个事件 for i in range(1, n + 1): time_required = t[i - 1] # 第 i 个事件的时间需求 energy_required = h[i - 1] # 第 i 个事件的精力需求 happiness = a[i - 1] # 第 i 个事件的快乐值 # 遍历所有可能的时间和精力组合 for j in range(T + 1): for k in range(H + 1): # 不选择第 i 个事件 dp[i][j][k] = dp[i - 1][j][k] # 选择第 i 个事件，如果满足时间和精力的限制 if j >= time_required and k >= energy_required: dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - time_required][k - energy_required] + happiness) # 返回最大快乐值，考虑所有事件和时间精力限制 return dp[n][T][H] # 测试样例 print(max_happiness(2, 2, 2, [1, 3], [3, 1], [3, 4])) # 输出: 0 print(max_happiness(3, 5, 5, [2, 1, 3], [1, 3, 2], [10, 7, 8])) # 输出: 18 print(max_happiness(1, 3, 3, [4], [4], [5])) # 输出: 0

复杂度分析：

时间复杂度：O(n * T * H)，其中 n 是事件的数量，T 是最大时间限制，H 是最大精力限制。 空间复杂度：O(n * T * H)，因为我们需要一个三维数组来存储状态。 优化：

如果 T 和 H 较大时，使用三维 DP 数组会导致空间复杂度过高。可以考虑将 DP 数组优化为二维数组，使用滚动数组的技巧来降低空间复杂度：

def solution(n: int, T: int, H: int, t: list, h: list, a: list) -> int: # 初始化 DP 数组 dp = [[0] * (H + 1) for _ in range(T + 1)] # 遍历每个事件 for i in range(n): time_required = t[i] energy_required = h[i] happiness = a[i] # 逆向遍历时间和精力，防止当前事件重复计算 for j in range(T, time_required - 1, -1): for k in range(H, energy_required - 1, -1): dp[j][k] = max(dp[j][k], dp[j - time_required][k - energy_required] + happiness) # 返回最大快乐值，考虑所有事件和时间精力限制 return dp[T][H]

这种优化方法将 空间复杂度 降低为 O(T * H)，但时间复杂度保持不变。

网址：刷题记录 414.小U生活事件快乐值最大化414.小U生活事件快乐值最大化 问题描述 小U喜欢分享她的日常生活。她有n个 https://www.yuejiaxmz.com/news/view/617075

相关内容

刷题实践选题：小U生活事件快乐值最大化问题
怎么解决u盘内存变小的问题
乐活U净时光：尽情享受放松愉悦的休闲生活
U净生活乐趣探索：发现休闲生活的无限乐趣
生活中21件让你快乐的小事
U净生活，净化空气，净化心情
情绪管理与快乐生活课件
U净：净化空气，净化心灵，净化生活
a t t i t u d e | 通过食物讲述生活哲学
生活事件压力管理,生活事件压力管理方法

随便看看