求下面背包问题的最优解:n=6, M=20,(p1,p2,…,p6)= (11,8,15,18,12,6), (W1,W2, …,W6) = (5,3,2,10,4,2)
时间: 2023-10-05 17:13:13 浏览: 54
可以使用动态规划算法来解决背包问题。设f[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。则有状态转移方程:
f[i][j] = max(f[i-1][j], f[i-1][j-Wi]+pi)
其中,f[i-1][j]表示不放第i个物品的最大价值,f[i-1][j-Wi]+pi表示放第i个物品的最大价值。如果第i个物品的重量Wi大于背包容量j,则无法放入背包中,此时f[i][j]=f[i-1][j]。
根据状态转移方程,可以填充下面的表格:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
2 0 0 0 8 8 11 11 11 19 19 19 19 19 19 19 19 19 19 19 19 19
3 0 0 15 15 15 15 26 26 26 34 34 34 34 34 34 34 34 34 34 34 34
4 0 0 15 15 18 18 26 26 33 33 33 49 49 49 49 49 49 49 49 49 49
5 0 12 15 15 18 30 30 30 33 45 45 49 49 61 61 61 61 61 61 61 61
6 0 12 18 24 24 30 30 36 36 45 51 51 57 57 67 67 67 67 67 67 67
因此,最优解为67。