PHP 動態規劃解決 0-1 背包問題：二維 DP 表完整實作

問題定義

背包容量 W，n 個物品（重量 w[i]，價值 v[i]），每項限取 0 或 1。求最大總價值。

動態規劃核心思路

定義 dp[i][w] = 前 i 個物品、容量 w 時的最大價值。狀態轉移：

dp[i][w] = max(
    dp[i-1][w],                    // 不拿第 i 項
    dp[i-1][w - w[i]] + v[i]       // 拿第 i 項（需 w >= w[i]）
)

完整實作（空間優化至一維）

<?php
function knapsackDP(array $weights, array $values, int $capacity): array {
    $n = count($weights);
    // 一維 DP 陣列：dp[w] = 容量 w 時的最大價值
    $dp = array_fill(0, $capacity + 1, 0);
    // 追蹤選擇路徑（選擇矩陣）
    $choice = array_fill(0, $n, array_fill(0, $capacity + 1, false));
    
    for ($i = 1; $i <= $n; $i++) {
        $w = $weights[$i - 1];
        $v = $values[$i - 1];
        
        // 逆序遍歷容量（關鍵：避免重複使用同一物品）
        for ($c = $capacity; $c >= $w; $c--) {
            $newValue = $dp[$c - $w] + $v;
            if ($newValue > $dp[$c]) {
                $dp[$c] = $newValue;
                $choice[$i - 1][$c] = true;
            }
        }
    }
    
    // 回溯找出選擇的物品
    $selected = [];
    $c = $capacity;
    for ($i = $n - 1; $i >= 0; $i--) {
        if ($choice[$i][$c]) {
            $selected[] = $i; // 物品索引
            $c -= $weights[$i];
        }
    }
    $selected = array_reverse($selected);
    
    return [
        'max_value' => $dp[$capacity],
        'selected_items' => $selected,
        'total_weight' => array_sum(array_intersect_key($weights, array_flip($selected))),
        'dp_table' => $dp, // 除錯用
    ];
}

// 測試
$weights = [3, 4, 5, 6];
$values = [8, 7, 4, 9];
$capacity = 15;

$result = knapsackDP($weights, $values, $capacity);
echo "最大價值：{$result['max_value']}\n";
echo "選擇物品索引：" . implode(', ', $result['selected_items']) . "\n";
echo "總重量：{$result['total_weight']}\n";

// 輸出 DP 表（除錯）
echo "\nDP 表 (容量 0-$capacity):\n";
for ($c = 0; $c <= $capacity; $c++) {
    echo "$c:{$result['dp_table'][$c]} ";
}
echo "\n";
?>

二維 DP 表版本（教學用、易理解）

function knapsackDP2D(array $weights, array $values, int $capacity): array {
    $n = count($weights);
    $dp = array_fill(0, $n + 1, array_fill(0, $capacity + 1, 0));
    
    for ($i = 1; $i <= $n; $i++) {
        for ($w = 0; $w <= $capacity; $w++) {
            // 不拿
            $dp[$i][$w] = $dp[$i-1][$w];
            // 拿（如果裝得下且更好）
            if ($weights[$i-1] <= $w) {
                $val = $dp[$i-1][$w - $weights[$i-1]] + $values[$i-1];
                if ($val > $dp[$i][$w]) {
                    $dp[$i][$w] = $val;
                }
            }
        }
    }
    return $dp;
}

空間複雜度優化說明

擴充：多重背包、完全背包

// 完全背包（每項無限取）：正序遍歷容量
for ($c = $w; $c <= $capacity; $c++) {
    $dp[$c] = max($dp[$c], $dp[$c - $w] + $v);
}

// 多重背包（每項限 k 次）：二進制拆分或單調隊列優化
// 將 k 拆分為 1, 2, 4, ..., k-2^m+1 多個 0-1 物品

測試案例驗證

// 經典測案
$w = [2, 2, 6, 5, 4];
$v = [6, 3, 5, 4, 6];
$cap = 10;
// 最優：項目 0,1,4 (重量 2+2+4=8, 價值 6+3+6=15)
// 或項目 0,3 (重量 2+5=7, 價值 6+4=10) ... 實際跑程式驗證
$result = knapsackDP($w, $v, $cap);
echo "測試案例最大價值：{$result['max_value']}\n";
?>

結語

0-1 背包動態規劃是經典 DP 入門題。關鍵點：逆序遍歷容量 實現空間優化、狀態轉移方程正確性、回溯重構解。實務上 W 較大（>10^5）時需考慮價值為維度的 DP 或近似演算法。