0-1背包问题中n=5,c=10,w[]={3,2,4,4,6},v[]={6,4,3,6,5},设m[i][j]是背包容量为j,可选物品为{i,i+1,...,n}时背包问题最优值,则当可选物品只有最后三个物品时,背包的最大价值是( ) A. 10 B. 9 C. 11 D. 8
时间: 2023-06-11 11:09:12 浏览: 92
0-1背包问题_.java给定背包的容量c,物品数量n、物品重量的集合w[n]和物品价值的集合
5星 · 资源好评率100%
我们可以使用动态规划来解决这个问题,状态转移方程为:
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i])
其中,m[i][j]表示背包容量为j,可选物品为{i,i+1,...,n}时背包问题最优值。
根据题意,可选物品只有最后三个物品,即{i=3,4,5},背包的容量为c=10。因此,我们需要计算m[3][10]。
首先,根据状态转移方程,我们需要先计算m[4][10]和m[4][6]。
m[4][10] = max(m[5][10], m[5][4]+5) = max(0, 5+5) = 10
m[4][6] = max(m[5][6], m[5][2]+5) = max(0, 0+5) = 5
接下来,我们可以计算m[3][10]:
m[3][10] = max(m[4][10], m[4][10-4]+6) = max(10, 6+6) = 12
因此,可选物品只有最后三个物品时,背包的最大价值是12。答案为D. 8是错误的选项。
阅读全文