用动态规划求如下解0/1 背包问题 (第八题)

时间:2020-12-30 04:23:40

用动态规划求如下解0/1 背包问题。(给出递归式,然后填表)

给定4个物体,其重量分别为2, 6, 5, 4,价值分别为:6, 5, 4, 6,背包的载重量为11,求装入背包的物体及其总价值.

用动态规划求如下解0/1 背包问题 (第八题)

初始:P(5) ={(0,0)},(w4,v4)=(4,6)

Q(5)= P(5) +(w4,v4) = {(4,6)}

P(4)= P(5)||Q(5)= {(0,0),(4,6)}

Q(4)= P(4) + (w3,v3) = {(5,4),(9,10)}

P(3)= P(4)||Q(4)= {(0,0),(4,6),(5,4),(9,10)} = {(0,0),(4,6),(9,10)}

Q(3)= P(3) + (w2,v2) = {(6,5),(10,11)}

P(2)= P(3)||Q(3)= {(0,0),(4,6),(6,5),(9,10),(10,11)} = {(0,0),(4,6),(9,10),(10,11)}

Q(2)= P(2) + (w1,v1) = {(2,6),(6,12)}

P(1)= P(2)||Q(2) = {(0,0),{2,6},(4,6),(6,12),(9,10),(10,11)}

即最优值为12,装入物体为:1,4