PHP 貪婪演算法解決 0-1 背包問題：單位價值優先策略

問題定義

背包容量 W，n 個物品各有重量 w[i] 與價值 v[i]。每種物品只能拿 0 或 1 個（0-1 背包），求最大總價值。

⚠️ 重要：貪婪演算法無法保證 0-1 背包的最優解，僅能得到近似解。0-1 背包最優解需用動態規劃（見下一篇）。本文展示貪婪策略作為教學與近似參考。

貪婪策略：單位價值遞減排序

<?php
class Item {
    public int $weight;
    public int $value;
    public float $ratio; // 單位價值
    
    public function __construct(int $weight, int $value) {
        $this->weight = $weight;
        $this->value = $value;
        $this->ratio = $value / $weight;
    }
}

function knapsackGreedy(array $items, int $capacity): array {
    // 1. 按單位價值遞減排序
    usort($items, fn($a, $b) => $b->ratio <=> $a->ratio);
    
    $totalValue = 0;
    $totalWeight = 0;
    $selected = [];
    
    // 2. 依序嘗試裝入
    foreach ($items as $item) {
        if ($totalWeight + $item->weight <= $capacity) {
            $selected[] = $item;
            $totalWeight += $item->weight;
            $totalValue += $item->value;
        }
    }
    
    return [
        'selected' => $selected,
        'total_weight' => $totalWeight,
        'total_value' => $totalValue,
        'remaining_capacity' => $capacity - $totalWeight,
    ];
}

// 測試資料
$items = [
    new Item(6, 30),  // ratio 5.0
    new Item(3, 14),  // ratio 4.67
    new Item(4, 16),  // ratio 4.0
    new Item(2, 9),   // ratio 4.5
];

$result = knapsackGreedy($items, 10);
echo "貪婪解：價值 {$result['total_value']}，重量 {$result['total_weight']}\n";
// 輸出：價值 49，重量 10 (選 6+3+? 實際需跑程式驗證)
?>

反例：貪婪非最優

容量 = 10

• 貪婪選 A(6) + 無法再裝 = 30
• 最優選 B(5) + C(4) = 42（剩 1 空間）

分數背包：貪婪可得最優解

若物品可分割（分數背包），貪婪演算法即為最優解：

function fractionalKnapsack(array $items, int $capacity): float {
    usort($items, fn($a, $b) => $b->ratio <=> $a->ratio);
    
    $value = 0;
    foreach ($items as $item) {
        if ($capacity >= $item->weight) {
            $value += $item->value;
            $capacity -= $item->weight;
        } else {
            $value += $item->ratio * $capacity; // 裝入部分
            break;
        }
    }
    return $value;
}

效能比較

結語

貪婪演算法以單位價值排序解 0-1 背包，程式簡單、速度快，但不保證最優。教學上可作為動態規劃的對比基準；實務上若需精確解請用 DP，若 W 極大可考慮 FPTAS（全多項式近似方案）或啟發式演算法。