预置示例
5件物品装入容量为8的背包，最大化总利润
问题参数
问题形式
max4x1 + 5x2 + 3x3 + 4x4 + 3x5
s.t.3x1 + 4x2 + 2x3 + 3x4 + 2x5 ≤ 8
xj ∈ { 0, 1 }, j = 1…5
| 变量 | x1 | x2 | x3 | x4 | x5 |
|---|---|---|---|---|---|
| 利润 p | 4 | 5 | 3 | 4 | 3 |
| 重量 w | 3 | 4 | 2 | 3 | 2 |
容量 W = 8
算法结果
最优值
11
节点数
9
最优解
[1, 0, 1, 1, 0]
步骤 1 / 20
0-1背包分支定界。共 5 个变量，按效率比 c/a 降序排列：x3, x5, x1, x4, x2
120
速度:
步骤日志
1.0-1背包分支定界。共 5 个变量，按效率比 c/a 降序排列：x3, x5, x1, x4, x2
2.探索节点 0（深度 0），已固定为1: []，已固定为0: []
3.节点 0 的 LP 上界 = 11.3333，LP解分数。选择 x4 进行分支。
4.探索节点 2（深度 1），已固定为1: [x4]，已固定为0: []
5.节点 2 的 LP 上界 = 11.3333，LP解分数。选择 x1 进行分支。
6.探索节点 4（深度 2），已固定为1: [x4,x1]，已固定为0: []
7.节点 4 得到整数可行解，目标值 = 11，更新下界。
8.探索节点 3（深度 2），已固定为1: [x4]，已固定为0: [x1]
9.节点 3 的 LP 上界 = 11.25，LP解分数。选择 x2 进行分支。
10.探索节点 6（深度 3），已固定为1: [x4,x2]，已固定为0: [x1]
11.节点 6 上界 10.5 ≤ 当前最优值 11，剪枝。
12.探索节点 5（深度 3），已固定为1: [x4]，已固定为0: [x1,x2]
13.节点 5 上界 10 ≤ 当前最优值 11，剪枝。
14.探索节点 1（深度 1），已固定为1: []，已固定为0: [x4]
15.节点 1 的 LP 上界 = 11.25，LP解分数。选择 x2 进行分支。
16.探索节点 8（深度 2），已固定为1: [x2]，已固定为0: [x4]
17.节点 8 上界 11 ≤ 当前最优值 11，剪枝。
18.探索节点 7（深度 2），已固定为1: []，已固定为0: [x4,x2]
19.节点 7 上界 10 ≤ 当前最优值 11，剪枝。
20.分支定界完成。最优解: x1=1, x2=0, x3=1, x4=1, x5=0，最优值 = 11