C語言貪心算法實現：分數背包問題（可分割物品）

問題定義

背包容量 M，n 個物品，每個有重量 wᵢ、價值 pᵢ。可任意分割物品（裝入比例 xᵢ ∈ [0,1]），求最大總價值。

貪心策略

按單位價值 vᵢ = pᵢ / wᵢ 遞減排序，依序裝入：

1. 若剩餘容量 ≥ wᵢ，整個裝入 (xᵢ=1)。
2. 否則裝入剩餘容量比例 (xᵢ = M_remaining / wᵢ)，背包滿，結束。

完整實現（兩種排序版本）

版本一：氣泡排序（教學用）

struct Bag { int id, weight, price; float unit; float taken; };

void Sort(struct Bag a[], int n) {
    for (int i=0; i<n; i++) a[i].unit = (float)a[i].price / a[i].weight;
    for (int i=0; i<n-1; i++)
        for (int j=0; j<n-i-1; j++)
            if (a[j].unit < a[j+1].unit) { swap(a[j], a[j+1]); }
}

void seekBest(struct Bag a[], int n, float cap) {
    for (int i=0; i<n; i++) {
        if (a[i].weight > cap) { a[i].taken = cap / a[i].weight; break; }
        a[i].taken = 1;
        cap -= a[i].weight;
    }
    // 輸出結果...
}

版本二：歸併排序（O(n log n)，工程級）

struct Object { int id; float p, w, v; }; // v = p/w

void MERGE(Object A[], int low, int mid, int high) {
    Object *B = malloc((high-low+1)*sizeof(Object));
    int h=low, i=0, j=mid+1;
    while (h<=mid && j<=high)
        B[i++] = (A[h].v >= A[j].v) ? A[h++] : A[j++];
    while (h<=mid) B[i++] = A[h++];
    while (j<=high) B[i++] = A[j++];
    for (int k=low, i=0; k<=high; k++) A[k] = B[i++];
    free(B);
}

void MERGESORT(Object A[], int low, int high) {
    if (low < high) {
        int mid = (low+high)/2;
        MERGESORT(A, low, mid);
        MERGESORT(A, mid+1, high);
        MERGE(A, low, mid, high);
    }
}

float knapsack_greedy(float m, Object a[], float x[], int n) {
    for (int i=0; i<n; i++) { a[i].v = a[i].p / a[i].w; x[i]=0; }
    MERGESORT(a, 0, n-1);
    float total = 0;
    for (int i=0; i<n; i++) {
        if (a[i].w <= m) { x[i]=1; m -= a[i].w; total += a[i].p; }
        else { x[i] = m / a[i].w; total += x[i]*a[i].p; break; }
    }
    return total;
}

關鍵點

• 分數背包貪心選擇性質成立：單位價值最高的物品優先裝入一定能得到全域最優解（證明：交換論法）。
• 0/1 背包（不可分割）不能用貪心，需動態規劃。
• 排序是效能瓶頸，工程上必須用 O(n log n) 排序（快排/歸併/堆排）。
• 輸出 x[i] 為裝入比例，實際重量 = x[i] * wᵢ。

測試範例

物品: (價值,重量) = (5,4), (6,7), (7,4), (9,3), (13,6)
容量: 15
排序後單位價值: 3.0, 2.33, 1.75, 1.25, 0.86
裝入: 全拿 4+3+4=11, 剩 4 → 第4項拿 4/6
總價值 = 9+13+7 + (4/6)*6 = 33

分數背包是貪心算法最經典的教科書級應用，理解其「貪心選擇性質」與「最優子結構」是演算法分析的基石。