Python写程序:动态规划实现0-1背包问题
时间: 2023-07-20 18:45:50 浏览: 77
好的,下面是Python实现0-1背包问题的动态规划算法:
```python
def knapsack_dp(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 j >= weights[i - 1]:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][capacity]
```
其中,`weights`表示每个物品的重量,`values`表示每个物品的价值,`capacity`表示背包容量。`dp`是动态规划数组,`dp[i][j]`表示前`i`个物品在背包容量为`j`的情况下能够获得的最大价值。初始状态为`dp[0][j] = 0`和`dp[i][0] = 0`。
在每次更新`dp[i][j]`时,如果当前背包容量`j`大于等于第`i`个物品的重量`weights[i - 1]`,则可以选择将第`i`个物品放入背包中,此时最大价值为不放第`i`个物品时的最大价值`dp[i - 1][j]`和放入第`i`个物品后的最大价值`dp[i - 1][j - weights[i - 1]] + values[i - 1]`中的较大值。如果当前背包容量`j`小于第`i`个物品的重量`weights[i - 1]`,则不能放入第`i`个物品,此时最大价值为不放第`i`个物品时的最大价值`dp[i - 1][j]`。
最终返回`dp[n][capacity]`即可,其中`n`为物品数量。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)