预置示例
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
10
速度:
步骤日志
通过分支定界搜索 0-1 背包的最优装载方案。LP 松弛提供上界，DFS 搜索分支树，剪支策略减少计算量。
5件物品装入容量为8的背包，最大化总利润
| 变量 | x1 | x2 | x3 | x4 | x5 |
|---|---|---|---|---|---|
| 利润 p | 4 | 5 | 3 | 4 | 3 |
| 重量 w | 3 | 4 | 2 | 3 | 2 |