貪心算法經典應用三：背包問題與 0-1 背包的 C 語言實現及最優性差異分析

編輯：關於C語言

問題定義

給定 n 種物品，第 i 種物品重量 w[i]，價值 v[i]；背包容量為 c。目標是選擇物品裝入背包，使總價值最大。根據物品是否可分割，分為兩類：

分數背包問題：物品可任意分割，可裝入部分。
0-1 背包問題：物品不可分割，只能整件裝入或不裝。

貪心策略的度量標準選擇

面對多維度屬性（價值、重量），貪心算法需確定單一決策指標：

度量標準	缺點
單純價值 v[i]	高價值物品可能過重，導致裝入極少
單純重量 w[i]	輕物品價值可能極低，浪費容量
單位價值 v[i]/w[i]	綜合考量「性價比」，為最優指標

因此，貪心策略為：按單位價值由高到低排序，依序裝入。

演算法流程

計算所有物品單位價值 v[i]/w[i]；
按單位價值非遞增排序；
依序嘗試裝入：
- 分數背包：若剩餘容量不足裝下整件，裝入該物品的一部分（比例 = 剩餘容量 / 物品重量），背包滿即停止。
- 0-1 背包：若剩餘容量不足裝下整件，直接跳過該物品，嘗試下一件；直到所有物品處理完畢或背包無法裝入任何剩餘物品。

C 語言完整實現

#include <stdio.h>
#include <stdlib.h>

void package(int n, float c, float v[], float w[], float x[]);
void package0_1(int n, float c, float v[], float w[], float x[]);

int main(void) {
    int n = 3;
    float c = 20;
    float v[] = {24, 15, 25};
    float w[] = {15, 10, 18};  // 已按單位價值降序：1.6, 1.5, 1.388...
    float *x = (float*)malloc(sizeof(float) * n);

    printf("****** 分數背包 *******\n");
    package(n, c, v, w, x);
    printf("******* 0-1 背包 ******\n");
    package0_1(n, c, v, w, x);
    system("PAUSE");
    free(x);
    return 0;
}

/* 分數背包：可裝入部分物品 */
void package(int n, float c, float v[], float w[], float x[]) {
    int i;
    for (i = 0; i < n; i++) x[i] = 0.0;

    for (i = 0; i < n; i++) {
        if (w[i] > c) break;          // 無法裝下整件
        x[i] = 1.0;                   // 整件裝入
        c -= w[i];
        printf("放入第%d件物品，背包剩餘容量 %.2f\n", i+1, c);
    }
    if (i < n) {                      // 還有物品且背包未滿，裝入部分
        x[i] = c / w[i];
        printf("放入第%d件物品的 %.2f 部分，背包剩餘容量 0\n", i+1, x[i]);
    }
}

/* 0-1 背包：只能整件裝入或不裝 */
void package0_1(int n, float c, float v[], float w[], float x[]) {
    int i;
    for (i = 0; i < n; i++) x[i] = 0.0;

    for (i = 0; i < n; i++) {
        if (w[i] > c) break;          // 無法裝下整件，跳過
        x[i] = 1.0;
        c -= w[i];
        printf("放入第%d件物品，背包剩餘容量 %.2f\n", i+1, c);
    }
    // 無法裝入部分物品，循環結束即為最終方案
}