PHP回溯法解決0-1背包問題：分支限界策略深度解析

回溯法與分支限界：另一種解決 0-1 背包的思路

動態規劃屬於「自底向上」填表，而回溯法則是「自頂向下」搜索狀態空間樹。配合分支限界剪枝，可大幅減少無效搜索，適合物品數量較大但承重較小的場景。

核心概念

• 狀態空間樹：每層決定一件物品「取」或「不取」，深度為 n，葉子節點代表完整方案。
• 約束函數：當前累計重量不得超過 W。
• 限界函數：估算以當前節點為根的子樹中可能達到的最大價值上界。若上界 ≤ 當前最優解，直接剪枝。

上界估算策略（貪心松弛）

將剩餘物品按單位價值 v/w 降序排列，允許「分數裝包」計算上界：

function bound($cp, $cw, $k, $W) {
    global $v_arr, $w_arr, $n;
    $b = $cp; $c = $cw;
    for ($i = $k + 1; $i < $n; $i++) {
        $c += $w_arr[$i];
        if ($c < $W) {
            $b += $v_arr[$i];
        } else {
            $b += (1 - ($c - $W) / $w_arr[$i]) * $v_arr[$i];
            break;
        }
    }
    return $b;
}

完整搜索流程

<?php
$v_arr = [11, 21, 31, 33, 43, 53, 55, 65];
$w_arr = [1, 11, 21, 23, 33, 43, 45, 55];
$n = count($w_arr);
$W_total = 110;

$bestV = -1; $bestX = [];
$Y = array_fill(0, $n, 0);
$cw = $cp = 0; $k = 0;

while (true) {
    // 向左走：盡量裝入
    while ($k < $n && $cw + $w_arr[$k] <= $W_total) {
        $cw += $w_arr[$k];
        $cp += $v_arr[$k];
        $Y[$k] = 1;
        $k++;
    }
    // 到達葉子或無法再裝入
    if ($k == $n) {
        if ($cp > $bestV) { $bestV = $cp; $bestX = $Y; }
        $k = $n - 1;
    } else {
        $Y[$k] = 0; // 嘗試不裝入
    }
    // 回溯 + 剪枝
    while ($k >= 0 && $Y[$k] != 1) $k--;
    if ($k < 0) break; // 搜索結束
    // 撤銷第 k 件
    $Y[$k] = 0;
    $cw -= $w_arr[$k];
    $cp -= $v_arr[$k];
    // 剪枝判斷
    while ($k >= 0 && bound($cp, $cw, $k, $W_total) <= $bestV) {
        while ($k >= 0 && $Y[$k] != 1) $k--;
        if ($k < 0) break 2;
        $Y[$k] = 0;
        $cw -= $w_arr[$k];
        $cp -= $v_arr[$k];
    }
    $k++;
}
echo "最優價值: $bestV\n方案: " . implode(',', $bestX);

優缺點對比

實際項目中可根據數據規模靈活選擇，甚至混合使用（如先用貪心得初始解作為下界）。