内容发布更新时间 : 2024/11/1 7:28:32星期一 下面是文章的全部内容请认真阅读。
约束条件: 如何剪枝?:
设r是当前尚未考虑的剩余物品价值总和;Cv是当前价值;bestv是当前最优价值。
当r+Cv≤bestv时,可剪去右子树。
11,请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10},
价值为{20, 30, 25},背包容量为25时搜索空间树。 答:
解空间树:
1
1
0
2
1
0
1
9
0
3
0
1
6
10
0
3
0
1
0
1
1
4
5
7 8 11
12 14 15
搜索空间树:
1
1
0
2
1 1
0
10
0
1
0 1
9
0 13
1
0
6
不可行解
8 价值=20
11
价值=55
12 价值=30
14 价值=25
15 价值=0