PHP貪婪算法求解0-1背包：近似最優與代碼實戰

貪婪策略：用局部最優換取全局近似

貪婪算法不保證 0-1 背包的全局最優解，但能在 O(n log n) 時間內給出不錯的近似解，適合對精度要求不極高、數據量極大的場景。核心思想：按「單位價值」v/w 降序排序，依序嘗試裝入。

算法步驟

1. 計算每件物品的性價比 ratio = value / weight。
2. 按 ratio 從大到小排序。
3. 遍歷排序後列表，若剩餘容量 ≥ 物品重量則整件裝入；否則跳過（0-1 特性，不允許切分）。

PHP 面向對象實現

<?php
class Item {
    public $weight;
    public $value;
    public $ratio;
    public function __construct($w, $v) {
        $this->weight = $w;
        $this->value  = $v;
        $this->ratio  = $v / $w;
    }
}

function greedyKnapsack(array $items, int $capacity): array {
    // 按 ratio 降序
    usort($items, fn($a, $b) => $b->ratio <=> $a->ratio);
    $totalValue = 0;
    $selected = [];
    foreach ($items as $item) {
        if ($item->weight <= $capacity) {
            $capacity -= $item->weight;
            $totalValue += $item->value;
            $selected[] = $item;
        }
    }
    return ['value' => $totalValue, 'items' => $selected];
}

// 測試數據
$items = [
    new Item(3, 8), new Item(4, 7), new Item(5, 4), new Item(6, 9),
    new Item(2, 5), new Item(7, 12), new Item(1, 3)
];
$capacity = 15;
$result = greedyKnapsack($items, $capacity);
echo "貪婪解總價值: {$result['value']}\n";
echo "選中物品數: " . count($result['items']) . "\n";

何時失效？

經典反例：容量 10，物品 A(6, 12)、B(5, 9)、C(5, 9)。貪婪先拿 A(ratio=2)，剩餘 4 無法裝 B/C，總價值 12；最優解應拿 B+C 價值 18。故貪婪解可能差距較大。

改進方向

• 結合動態規劃：小容量用 DP，大容量用貪婪作為初始解加速分支限界。
• 啟發式調整：嘗試交換已選/未選物品進行局部優化（如 2-opt）。

理解貪婪的邊界，才能在工程中做正確的權衡。