解题思路:
注意事项:
参考代码:
def find_cakes(cakes, m): # 初始化动态规划数组,dp[i][j]表示前i个小蛋糕中选择若干个,美味度之和为j所需的最小数量 n = len(cakes) dp = [[float('inf')] * (m + 1) for _ in range(n + 1)] # 初始状态,前0个小蛋糕,美味度之和为0所需的数量为0 for i in range(n + 1): dp[i][0] = 0 # 动态规划递推 for i in range(1, n + 1): for j in range(1, m + 1): # 如果当前小蛋糕的美味度大于当前目标和,不选择当前小蛋糕 if cakes[i - 1] > j: dp[i][j] = dp[i - 1][j] else: # 选择当前小蛋糕或者不选择,取最小值 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - cakes[i - 1]] + 1) # 如果最终的dp[n][m]仍然为inf,表示无法达到目标和 if dp[n][m] == float('inf'): return "><" return dp[i][j] a, b = map(int, input().strip().split()) obj = [] for i in range(b): m, n=map(int,input().strip().split()) for j in range(n): obj.append(m) cakes = obj target_deliciousness = a result = find_cakes(cakes, target_deliciousness) print(result)
0.0分
0 人评分
兰顿蚂蚁 (C++代码)浏览:1097 |
不容易系列 (C语言代码)浏览:670 |
简单的a+b (C语言代码)浏览:600 |
三角形 (C++代码)递归(存在大量重复计算,容易出现时间超限)浏览:781 |
C语言训练-数字母 (C语言代码)浏览:608 |
P1000 (C语言代码)浏览:877 |
C语言训练-亲密数 (C语言描述,反正怎么都能对)浏览:2169 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:567 |
拆分位数 (C语言代码)浏览:444 |
非常简单的算法,题解1049:C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:620 |