PHP動態規劃實戰：0-1背包問題完整解析與代碼實現

PHP動態規劃解決0-1背包問題：核心邏輯與實戰代碼

0-1背包問題是經典的動態規範入門案例。場景很直觀：給定一個承重上限為 W 的背包，以及 n 件物品，每件物品有各自的重量 w[i] 和價值 v[i]。目標是在不超過承重限制的前提下，挑選物品使總價值最大化。每件物品只能選擇放入或不放入，不可拆分，這就是「0-1」的由來。

動態規劃狀態定義

我們定義二維陣列 dp[i][w] 表示：前 i 件物品中任意選擇，放入承重為 w 的背包所能獲得的最大價值。狀態轉移方程為：

dp[i][w] = max( dp[i-1][w], dp[i-1][w - weight[i]] + value[i] )

其中第一項代表不選第 i 件物品，第二項代表選擇該物品（前提是剩餘容量足夠）。初始條件為 dp[0][*] = 0 與 dp[*][0] = 0。

PHP 完整實現代碼

<?php
// 背包最大承重
$W = 15;
// 4 件物品的重量與價值
$weight = [3, 4, 5, 6];
$value  = [8, 7, 4, 9];
$n = count($weight);

// 初始化 dp 表 (n+1) x (W+1)
$dp = array_fill(0, $n + 1, array_fill(0, $W + 1, 0));

// 填表
for ($i = 1; $i <= $n; $i++) {
    for ($w = 1; $w <= $W; $w++) {
        // 不選第 i 件
        $dp[$i][$w] = $dp[$i-1][$w];
        // 選第 i 件（若容量允許）
        if ($weight[$i-1] <= $w) {
            $candidate = $dp[$i-1][$w - $weight[$i-1]] + $value[$i-1];
            if ($candidate > $dp[$i][$w]) {
                $dp[$i][$w] = $candidate;
            }
        }
    }
}

// 輸出最大價值
echo "最大價值: " . $dp[$n][$W] . PHP_EOL;

// 可選：回溯輸出被選中的物品
$w = $W;
for ($i = $n; $i >= 1; $i--) {
    if ($dp[$i][$w] != $dp[$i-1][$w]) {
        echo "選中物品 $i (重量:{$weight[$i-1]}, 價值:{$value[$i-1]})" . PHP_EOL;
        $w -= $weight[$i-1];
    }
}
?>

關鍵點總結

• 時間複雜度 O(nW)，空間複雜度同樣為 O(nW)；若僅需最大值可優化為一維陣列將空間降至 O(W)。
• 代碼中使用 array_fill 初始化二維陣列，避免未定義索引報錯。
• 回溯邏輯可輕鬆擴展以輸出具體裝包方案。

掌握此模板後，面對變體（如完全背包、多重背包）只需微調轉移方程即可。