用Python语言写一个完全背包算法,不导入库就可以使用,并且输出所放物品和价值,代码简洁
时间: 2024-10-13 19:15:13 浏览: 24
当然可以。完全背包算法(0-1 Knapsack Problem)是一个经典的动态规划问题,我们可以通过循环和条件判断来实现。这里是一个简单的Python代码示例:
```python
def knap_sack(weights, values, capacity):
n = len(weights)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
# 构建动态规划表
for i in range(1, n+1):
for w in range(1, capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
# 找出最优解并记录物品
selected_items = []
w = capacity
for i in reversed(range(n)):
if dp[i][w] != dp[i - 1][w]:
selected_items.append((i, weights[i], values[i]))
w -= weights[i]
return dp[n][capacity], selected_items
# 示例输入
weights = [2, 3, 4, 5]
values = [6, 9, 7, 10]
capacity = 8
max_value, items = knap_sack(weights, values, capacity)
print(f"最大价值:{max_value}")
print("选择的物品及价值:")
for item in items:
print(f"物品 {item[0]+1},重量 {item[1]},价值 {item[2]}")
#
阅读全文