给定6个物品,重量分别为(5,3,2,10,4,2),价值分别为(11,8,15,18,12,6),背包容量W=20,应用分支限界法求解0/1背包问题,请写出在解空间树上的详细搜索步骤,利用广度优先
时间: 2023-08-07 16:05:40 浏览: 763
首先,将物品按照单位重量的价值从大到小排序,得到顺序为(2,2,3,4,5,10),价值分别为(15,6,8,12,11,18)。
接下来,我们可以利用广度优先搜索的方式来搜索解空间树。
Step 1: 初始化根节点,背包容量为W=20,当前价值为0,当前物品编号为0。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
```
Step 2: 扩展根节点,生成其左右子节点。
左子节点代表不选当前物品,右子节点代表选当前物品。
对于左子节点,背包容量和当前物品编号不变,当前价值也不变。
对于右子节点,背包容量减去当前物品的重量,当前价值加上当前物品的价值,当前物品编号加1。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
右子节点:
节点编号:3
剩余容量:18
当前价值:15
当前物品编号:1
```
Step 3: 对右子节点进行剪枝。
由于右子节点所选物品的总重量已经超过了背包的容量,因此不需要再继续扩展其子节点。直接将右子节点从解空间树上删除。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
```
Step 4: 对左子节点进行扩展,生成其左右子节点。
对于左子节点,背包容量和当前物品编号不变,当前价值也不变。
对于右子节点,背包容量减去当前物品的重量,当前价值加上当前物品的价值,当前物品编号加1。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
右子节点:
节点编号:5
剩余容量:17
当前价值:15
当前物品编号:2
```
Step 5: 对右子节点进行剪枝。
由于右子节点所选物品的总重量已经超过了背包的容量,因此不需要再继续扩展其子节点。直接将右子节点从解空间树上删除。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
```
Step 6: 对左子节点的左子节点进行扩展,生成其左右子节点。
对于左子节点,背包容量和当前物品编号不变,当前价值也不变。
对于右子节点,背包容量减去当前物品的重量,当前价值加上当前物品的价值,当前物品编号加1。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
右子节点:
节点编号:7
剩余容量:15
当前价值:15
当前物品编号:3
```
Step 7: 对左子节点的右子节点进行剪枝。
由于右子节点所选物品的总重量已经超过了背包的容量,因此不需要再继续扩展其子节点。直接将右子节点从解空间树上删除。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
```
Step 8: 对左子节点的左子节点进行扩展,生成其左右子节点。
对于左子节点,背包容量和当前物品编号不变,当前价值也不变。
对于右子节点,背包容量减去当前物品的重量,当前价值加上当前物品的价值,当前物品编号加1。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
左子节点:
节点编号:8
剩余容量:20
当前价值:0
当前物品编号:4
右子节点:
节点编号:9
剩余容量:15
当前价值:12
当前物品编号:4
```
Step 9: 对左子节点的右子节点进行扩展,生成其左右子节点。
对于左子节点,背包容量和当前物品编号不变,当前价值也不变。
对于右子节点,背包容量减去当前物品的重量,当前价值加上当前物品的价值,当前物品编号加1。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
左子节点:
节点编号:8
剩余容量:20
当前价值:0
当前物品编号:4
左子节点:
节点编号:10
剩余容量:15
当前价值:11
当前物品编号:5
```
Step 10: 对左子节点的右子节点的左子节点进行剪枝。
由于右子节点所选物品的总重量已经超过了背包的容量,因此不需要再继续扩展其子节点。直接将右子节点从解空间树上删除。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
左子节点:
节点编号:8
剩余容量:20
当前价值:0
当前物品编号:4
左子节点:
节点编号:10
剩余容量:15
当前价值:11
当前物品编号:5
```
Step 11: 对左子节点的右子节点的右子节点进行剪枝。
由于右子节点所选物品的总重量已经超过了背包的容量,因此不需要再继续扩展其子节点。直接将右子节点从解空间树上删除。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
左子节点:
节点编号:8
剩余容量:20
当前价值:0
当前物品编号:4
```
Step 12: 对左子节点的右子节点的左子节点进行扩展,生成其左右子节点。
对于左子节点,背包容量和当前物品编号不变,当前价值也不变。
对于右子节点,背包容量减去当前物品的重量,当前价值加上当前物品的价值,当前物品编号加1。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
左子节点:
节点编号:8
剩余容量:20
当前价值:0
当前物品编号:4
左子节点:
节点编号:11
剩余容量:13
当前价值:11
当前物品编号:5
```
Step 13: 对左子节点的右子节点的左子节点的左子节点进行剪枝。
由于右子节点所选物品的总重量已经超过了背包的容量,因此不需要再继续扩展其子节点。直接将右子节点从解空间树上删除。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
左子节点:
节点编号:8
剩余容量:20
当前价值:0
当前物品编号:4
左子节点:
节点编号:11
剩余容量:13
当前价值:11
当前物品编号:5
```
Step 14: 对左子节点的右子节点的左子节点的右子节点进行剪枝。
由于右子节点所选物品的总重量已经超过了背包的容量,因此不需要再继续扩展其子节点。直接将右子节点从解空间树上删除。
```
节点编号:1
剩余容量:20
当前价值:0
当前物品编号:0
左子节点:
节点编号:2
剩余容量:20
当前价值:0
当前物品编号:1
左子节点:
节点编号:4
剩余容量:20
当前价值:0
当前物品编号:2
左子节点:
节点编号:6
剩余容量:20
当前价值:0
当前物品编号:3
左子节点:
节点编号:8
剩余容量:20
当前价值:0
当前物品编号:4
左子节点:
节点编号:11
剩余容量:13
当前价值:11
当前物品编号:5
```
Step 15: 搜索完毕,得到最优解为选取第1、2、4、5号物品,总重量为14,总价值为46。
解空间树如下图所示:
```
1
/ \
2 3
/ \
4 5
/ \ \
6 7 9
/ \ \
8 10 11
```