萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 回溯法解決 0-1 背包問題:分支限界優化與剪枝策略

前言

回溯法配合分支限界是解決 0-1 背包問題的另一經典路徑,適合物品數較少(N≤30)但容量極大(W≥10⁹)導致 DP 陣列不可行的場景。本文實作深度優先搜尋 + 上界剪枝,並分析最優優先搜尋(Best-First)變體。

核心思想

  • 搜尋樹:第 i 層決定第 i 件物品取/不取,葉節點為完整方案。
  • 上界函數:計算當前節點能達到的理論最大價值(含分數背包放寬),若 ≤ 當前最佳解,剪枝。
  • 節點優先級:優先展開上界高的節點(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

最優優先搜尋(Best-First / A* 風格)

使用優先隊列(最大堆),每次展開上界最高的節點:

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-MiddleO(N 2^{N/2})O(2^{N/2})N≤40, W 極大

Meet-in-the-Middle 實作大綱 (N≤40)

  1. 將物品分為兩半 A、B。
  2. 枚舉 A 所有子集 → (weight, value) 列表 LA,同理得 LB。
  3. 對 LA 按 weight 排序,並移除「被支配」點(weight 較大但 value 不更大)。
  4. 遍歷 LB,對每個 (w_b, v_b),在 LA 二分查找最大 weight ≤ W-w_b 的 value,更新最優解。

總結

回溯法透過「上界剪枝」將指數搜尋空間大幅壓縮,配合單位價值排序與 Best-First 搜尋,能高效解決中小規模、大容量的 0-1 背包。PHP 實作需注意遞歸深度限制(ini_set('xdebug.max_nesting_level', 1000))與優先隊列效能,實際專案中 N>30 建議改用 Meet-in-the-Middle 或整數規劃求解器(OR-Tools)。

copyright © 萬盛學電腦網 all rights reserved