背包問題
python
def knapsack(items, m):
n = len(items)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(m + 1):
weight, value = items[i - 1]
if weight <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)
else:
dp[i][w] = dp[i - 1][w]
return dp[n][m]
items = [(3, 4), (4, 5), (7, 10), (3, 8), (2, 6)]
m = 10
max_value = knapsack(items, m)
print("最大價值:", max_value)Contributors
lucashsu95