预置示例
5个元素须被选中的集合覆盖，最小化总费用
问题参数
问题形式
min3F₁ + 2F₂ + 4F₃ + 2F₄ + 3F₅
s.t.F₁ + F₂ ≥ 1（覆盖 e1）
s.t.F₂ + F₃ ≥ 1（覆盖 e2）
s.t.F₁ + F₃ + F₅ ≥ 1（覆盖 e3）
s.t.F₄ + F₅ ≥ 1（覆盖 e4）
s.t.F₂ + F₄ ≥ 1（覆盖 e5）
s.t.F₁, F₂, F₃, F₄, F₅ ∈ { 0, 1 }
| 元素 \ 集合 | F₁ | F₂ | F₃ | F₄ | F₅ |
|---|---|---|---|---|---|
| e1 | ✓ | ✓ | · | · | · |
| e2 | · | ✓ | ✓ | · | · |
| e3 | ✓ | · | ✓ | · | ✓ |
| e4 | · | · | · | ✓ | ✓ |
| e5 | · | ✓ | · | ✓ | · |
| 费用 c | 3 | 2 | 4 | 2 | 3 |
覆盖矩阵
| 元素↓ 集合→ | F₁ | F₂ | F₃ | F₄ | F₅ |
|---|---|---|---|---|---|
| e1 | 1 | 1 | 0 | 0 | 0 |
| e2 | 0 | 1 | 1 | 0 | 0 |
| e3 | 1 | 0 | 1 | 0 | 1 |
| e4 | 0 | 0 | 0 | 1 | 1 |
| e5 | 0 | 1 | 0 | 1 | 0 |
| 费用 | 3 | 2 | 4 | 2 | 3 |
10
速度:
步骤日志