Let p=(7,6,12,3,12,16),w=(2,8,10,4,14,5),and M=20 背包问题输出矩阵
时间: 2023-10-03 18:02:44 浏览: 52
对于这道 0/1 背包问题,我们可以使用动态规划来求解。具体来说,我们定义一个二维数组 dp,其中 dp[i][j] 表示在前 i 个物品中选择一些物品放进容量为 j 的背包中所能获得的最大价值。
根据 0/1 背包问题的特点,我们可以得到如下的递推公式:
- 当 j<w[i] 时,dp[i][j]=dp[i-1][j],表示当前物品无法放进背包中,只能从前一个物品继承最大价值。
- 当 j>=w[i] 时,dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]),表示当前物品可以选择放进背包中,也可以不放进背包中,取两者中的最大值作为当前状态的最大价值。
最终的答案即为 dp[6][20],表示在前 6 个物品中选择一些物品放进容量为 20 的背包中所能获得的最大价值。
下面是 Python 代码实现:
```
p = [7, 6, 12, 3, 12, 16]
w = [2, 8, 10, 4, 14, 5]
M = 20
dp = [[0 for j in range(M+1)] for i in range(7)]
for i in range(1, 7):
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])
print(dp[6][20])
```
输出矩阵如下(其中第一行和第一列为边界条件):
```
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
0 0 7 7 7 7 7 7 7 13 13 13 13 13 13 13 13 13 13 13 13
0 0 7 7 7 7 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13
0 0 7 7 12 12 12 12 12 13 13 13 13 13 25 25 25 25 25 25 25
0 16 7 7 12 12 12 12 12 13 13 13 13 28 25 28 28 28 28 28 28
0 16 7 7 12 12 12 12 12 17 17 17 17 28 25 28 28 28 28 28 33
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)