动态规划实现0-1背包问题 输入 M n P W n行 输出最优解及解向量 例如 入: 6 3 5 3 4 3 3 2 出: 9 1 1 0
时间: 2024-01-03 14:03:52 浏览: 25
好的,以下是动态规划实现0-1背包问题的Python代码:
```python
def knapsack(M, n, P, W):
# 创建一个二维数组来保存子问题的最优解
dp = [[0 for j in range(M + 1)] for i in range(n + 1)]
# 计算并保存子问题的最优解
for i in range(1, n + 1):
for j in range(1, M + 1):
if j < W[i - 1]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i - 1]] + P[i - 1])
# 从最优解的二维数组中反向查找解向量
j = M
res = []
for i in range(n, 0, -1):
if dp[i][j] > dp[i - 1][j]:
res.append(1)
j -= W[i - 1]
else:
res.append(0)
# 反转解向量并返回最优解和解向量
res.reverse()
return dp[n][M], res
```
接下来是使用样例数据的调用代码和输出结果:
```python
M = 6
n = 3
P = [5, 3, 4]
W = [3, 3, 2]
opt, vec = knapsack(M, n, P, W)
print(opt, end=' ')
print(' '.join(str(x) for x in vec))
```
输出结果为:
```
9 1 1 0
```
其中,第一个数字是最优解,后面的数字是解向量,其中1代表选择该物品,0代表不选择。