def knapsack(capacity, commodities):
n = len(commodities)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if commodities[i - 1][1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - commodities[i - 1][1]] + commodities[i - 1][2])
else:
dp[i][w] = dp[i - 1][w]
selected = [0] * n
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i - 1][w]:
selected[i - 1] = 1
w -= commodities[i - 1][1]
return dp[n][capacity], selected
def print_selected_commodities(commodities, selected):
print("选中的商品如下:")
for i, is_selected in enumerate(selected):
if is_selected:
name, weight, value = commodities[i]
print(f"{name} (重量: {weight} 磅, 价值: {value} 美元)")
def main():
commodities = [
("吉他", 15, 1500),
("笔记本电脑", 20, 2000),
("音响", 30, 3000)
]
capacity = 35
max_value, selected = knapsack(capacity, commodities)
print(f"最大价值: {max_value}")
print_selected_commodities(commodities, selected)
if __name__ == "__main__":
main()