0/1背包问题 动态规划 python代码
时间: 2023-10-22 15:18:54 浏览: 38
很高兴为您提供答案!关于0/1背包问题的动态规划Python代码,以下是一个标准的示例代码:
```
def knapSack(W, wt, val, n):
if n == 0 or W == 0 :
return 0
if (wt[n-1] > W):
return knapSack(W, wt, val, n-1)
else:
return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1))
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
```
这段代码就是实现了0/1背包问题的动态规划求解。其中,val数组存放了每个物品的价值,wt数组存放了每个物品的重量,W表示背包的最大承重,n表示物品的数量。运行上述代码,输出的结果是220,即背包能够承载的最大价值是220。
希望这能够帮助到您,有任何其他问题,欢迎随时向我提出!
相关问题
用动态规划算法求解0/1背包问题python完整代码
好的,下面是用动态规划算法求解0/1背包问题的Python完整代码:
```python
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity)) # 输出:11
```
其中,`weights`和`values`分别是物品的重量和价值的列表,`capacity`是背包的容量。`n`是物品的数量,`dp`是一个`(n+1)×(capacity+1)`的二维列表,`dp[i][j]`表示在前`i`个物品中选择不超过重量为`j`的物品可以得到的最大价值。
我们用两个嵌套的循环来遍历所有的物品和容量。当物品的重量超过当前容量时,我们无法选择这个物品,因此最大价值就是前`i-1`个物品的最大价值,即`dp[i-1][j]`。当物品的重量不超过当前容量时,我们可以选择这个物品,也可以不选择这个物品。如果不选择这个物品,最大价值就是前`i-1`个物品的最大价值,即`dp[i-1][j]`。如果选择这个物品,最大价值就是前`i-1`个物品中不超过重量为`j-weights[i-1]`的物品可以得到的最大价值,加上当前物品的价值,即`dp[i-1][j-weights[i-1]]+values[i-1]`。因此,我们在这两种情况中选择价值更大的方案,更新`dp[i][j]`的值。
最后,返回`dp[n][capacity]`即可得到在不超过背包容量的情况下可以得到的最大价值。
动态规划算法求解0/1背包问题代码
以下是动态规划算法求解0/1背包问题的Python代码:
```python
def knapsack(weights, values, capacity):
n = len(weights)
# 初始化二维数组,其中dp[i][j]表示前i件物品放入一个容量为j的背包可以获得的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# 从第1件物品开始遍历
for i in range(1, n + 1):
# 遍历容量从0到背包容量
for j in range(capacity + 1):
if weights[i - 1] > j:
# 如果当前物品的重量大于当前背包容量,则无法装入,直接使用上一次的最优解
dp[i][j] = dp[i - 1][j]
else:
# 否则,当前物品可以装入背包,需要比较装入和不装入的价值大小,取最大值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
```
其中,`weights`和`values`分别表示物品的重量和价值,`capacity`表示背包的容量,函数返回背包能够获得的最大价值。