回溯法配合分支限界是解決 0-1 背包問題的另一經典路徑,適合物品數較少(N≤30)但容量極大(W≥10⁹)導致 DP 陣列不可行的場景。本文實作深度優先搜尋 + 上界剪枝,並分析最優優先搜尋(Best-First)變體。
function bound(array $values, array $weights, int $n, int $capacity, int $level, int $currentWeight, int $currentValue): float {
if ($currentWeight >= $capacity) return 0.0;
$bound = $currentValue;
$weight = $currentWeight;
// 從下一層開始,盡可能裝入完整物品
for ($i = $level; $i < $n; $i++) {
if ($weight + $weights[$i] <= $capacity) {
$weight += $weights[$i];
$bound += $values[$i];
} else {
// 剩餘容量裝入部分物品(分數背包)
$remaining = $capacity - $weight;
$bound += $values[$i] * ($remaining / $weights[$i]);
break;
}
}
return $bound;
}
<?php
function knapsackBacktrack(array $weights, array $values, int $capacity): array {
$n = count($weights);
// 依單位價值排序,提升上界緊度
$indices = array_keys($weights);
usort($indices, fn($a, $b) => ($values[$b] / $weights[$b]) <=> ($values[$a] / $weights[$a]));
$sortedW = array_map(fn($i) => $weights[$i], $indices);
$sortedV = array_map(fn($i) => $values[$i], $indices);
$bestValue = 0;
$bestSelection = [];
$currentSelection = [];
function dfs(int $level, int $currentWeight, int $currentValue) use (
&$bestValue, &$bestSelection, &$currentSelection,
$sortedW, $sortedV, $n, $capacity
) {
global $callCount; $callCount++; // 統計遞歸次數
if ($level === $n) {
if ($currentValue > $bestValue) {
$bestValue = $currentValue;
$bestSelection = $currentSelection;
}
return;
}
// 計算上界
$ub = bound($sortedV, $sortedW, $n, $capacity, $level, $currentWeight, $currentValue);
if ($ub <= $bestValue) return; // 剪枝
// 嘗試取當前物品
if ($currentWeight + $sortedW[$level] <= $capacity) {
$currentSelection[] = $indices[$level];
dfs($level + 1, $currentWeight + $sortedW[$level], $currentValue + $sortedV[$level]);
array_pop($currentSelection);
}
// 嘗試不取
dfs($level + 1, $currentWeight, $currentValue);
}
$callCount = 0;
dfs(0, 0, 0);
return [
'max_value' => $bestValue,
'selected' => $bestSelection,
'nodes_visited' => $callCount,
];
}
// 測試
$weights = [10, 20, 30, 40, 50];
$values = [60, 100, 120, 200, 220];
$capacity = 100;
$result = knapsackBacktrack($weights, $values, $capacity);
echo "最大價值:{$result['max_value']}\n"; // 380
echo "選取索引:[" . implode(', ', $result['selected']) . "]\n";
echo "訪問節點:{$result['nodes_visited']}\n"; // 遠小於 2^5=32
使用優先隊列(最大堆),每次展開上界最高的節點:
use SplPriorityQueue;
function knapsackBestFirst(array $weights, array $values, int $capacity): array {
$n = count($weights);
$indices = array_keys($weights);
usort($indices, fn($a, $b) => ($values[$b] / $weights[$b]) <=> ($values[$a] / $weights[$a]));
$sortedW = array_map(fn($i) => $weights[$i], $indices);
$sortedV = array_map(fn($i) => $values[$i], $indices);
$pq = new SplPriorityQueue();
// 節點:[level, weight, value, selection, bound]
$rootBound = bound($sortedV, $sortedW, $n, $capacity, 0, 0, 0);
$pq->insert([0, 0, 0, [], $rootBound], $rootBound);
$bestValue = 0;
$bestSelection = [];
while (!$pq->isEmpty()) {
$node = $pq->extract();
[$level, $weight, $value, $selection, $ub] = $node;
if ($ub <= $bestValue) continue; // 即使入隊時最優,當前可能已被超越
if ($level === $n) {
if ($value > $bestValue) {
$bestValue = $value;
$bestSelection = $selection;
}
continue;
}
// 生成左子節點(取)
if ($weight + $sortedW[$level] <= $capacity) {
$newW = $weight + $sortedW[$level];
$newV = $value + $sortedV[$level];
$newSel = [...$selection, $indices[$level]];
$newUb = bound($sortedV, $sortedW, $n, $capacity, $level+1, $newW, $newV);
if ($newUb > $bestValue) {
$pq->insert([$level+1, $newW, $newV, $newSel, $newUb], $newUb);
}
}
// 生成右子節點(不取)
$newUb = bound($sortedV, $sortedW, $n, $capacity, $level+1, $weight, $value);
if ($newUb > $bestValue) {
$pq->insert([$level+1, $weight, $value, $selection, $newUb], $newUb);
}
}
return ['max_value' => $bestValue, 'selected' => $bestSelection];
}
| 方法 | 時間複雜度 | 空間複雜度 | 適用場景 |
|---|---|---|---|
| DP (二維) | O(NW) | O(NW) | N,W 均較小 (≤1000) |
| DP (1維) | O(NW) | O(W) | N≤1000, W≤10⁵ |
| 回溯 + 剪枝 | 指數 (最壞),實際極快 | O(N) 堆疊 | N≤30, W 極大 |
| Best-First | 同上,但常更快找到最優解 | O(2ᴺ) 最壞 | 需快速獲得可行解、並行化 |
| Meet-in-the-Middle | O(N 2^{N/2}) | O(2^{N/2}) | N≤40, W 極大 |
回溯法透過「上界剪枝」將指數搜尋空間大幅壓縮,配合單位價值排序與 Best-First 搜尋,能高效解決中小規模、大容量的 0-1 背包。PHP 實作需注意遞歸深度限制(ini_set('xdebug.max_nesting_level', 1000))與優先隊列效能,實際專案中 N>30 建議改用 Meet-in-the-Middle 或整數規劃求解器(OR-Tools)。