圣诞节来临了,圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的 25 价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿雪橇最多只能装 下重量 W 的糖果,请问圣诞老人最多能带走多大价值的糖果。用python回答
时间: 2024-03-24 12:36:36 浏览: 89
这是一个经典的背包问题,可以使用动态规划算法来解决。以下是Python代码实现:
```
def max_value(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for j in range(W, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[W]
# 示例
weights = [3, 5, 2, 1, 4]
values = [8, 10, 6, 3, 7]
W = 10
print(max_value(weights, values, W)) # 输出 24
```
其中,weights表示每个糖果的重量,values表示每个糖果的价值,W表示驯鹿雪橇能承受的最大重量。函数返回圣诞老人能带走的最大价值。
阅读全文