貪心算法入門：分數背包問題與 C++ 實現

貪心 vs 動態規劃

貪心算法：每步做局部最優選擇，期望達到全局最優。
動態規劃：基於最優子結構+重疊子問題，自底向上/自頂向下備忘錄。
關鍵區別：貪心無後悔，選擇後不再回溯；DP 可能通過子問題組合調整決策。

經典例題：分數背包問題

問題：n 件物品，第 i 件價值 v_i、重量 w_i。背包容量 W。可取物品任意比例。最大化總價值。
（對比：0-1 背包只能整件取捨，需 DP 解決）

貪心策略：按單位價值 v_i / w_i 降序排序，依次裝入

證明直覺：單位價值高的物品「性價比」最高，優先裝入不會損失最優解。若最優解未優先裝高性價比物品，可通過交換論證構造更優解，矛盾。

示例

背包容量 50。
按單位價值排序：1 → 2 → 3。
裝入 1（剩 40）→ 裝入 2（剩 20）→ 裝入 3 的 2/3（剩 0）。
總價值 = 60 + 100 + 120×(20/30) = 240。
0-1 背包最優為 220（裝 2+3），分數背包更優。

C++ 實現

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

struct Item {
    double value, weight;
    double unitValue() const { return value / weight; }
};

int main() {
    int n;
    double W;
    cout << "物品數量: "; cin >> n;
    cout << "背包容量: "; cin >> W;
    
    vector<Item> items(n);
    cout << "輸入 " << n << " 個物品的價值和重量:\n";
    for (int i = 0; i < n; ++i) cin >> items[i].value >> items[i].weight;
    
    sort(items.begin(), items.end(), 
         [](const Item &a, const Item &b) { return a.unitValue() > b.unitValue(); });
    
    double totalValue = 0;
    for (const auto &it : items) {
        if (W >= it.weight) {
            W -= it.weight;
            totalValue += it.value;
        } else {
            totalValue += W * it.unitValue(); // 取分數部分
            W = 0;
            break;
        }
    }
    
    cout << fixed << setprecision(2);
    cout << "最大價值: " << totalValue << endl;
    return 0;
}

貪心算法適用性判斷

並非所有問題皆適用貪心。兩大核心性質：

1. 貪心選擇性質：全局最優解可通過局部最優選擇構造（無後悔）
2. 最優子結構：子問題最優解構成全局最優解

常見貪心問題：

• 活動選擇 / 區間調度
• 霍夫曼編碼
• 最小生成樹
• 迪杰斯特拉最短路（非負權）
• 分數背包

總結

分數背包是貪心算法教科書級入門例題：排序+線性掃描，O(n log n) 時間，代碼簡潔。理解「單位價值排序」的交換論證，掌握貪心與 DP 的邊界，是算法進階的關鍵一步。