貪婪演算法應用：0/1 背包問題與 k-最優啟發式改進

編輯：關於C語言

貪婪演算法應用：0/1 背包問題與 k-最優啟發式改進

0/1 背包問題是經典 NP-hard 組合優化問題。單純貪婪策略 (依價值、重量、價值密度排序) **無法保證最優解**，但 **k-最優啟發式** 通過枚舉前 k 個項目的組合，可在 O(n^{k+1}) 時間內獲得 **誤差界 ≤ 100/(k+1)%** 的近似解。本文系統分析三種基本貪婪策略失效原因、k-最優演算法原理、完整範例演示與實務建議。

問題定義

輸入**：n 個物品，重量 w[i]，價值 p[i]，背包容量 c。
決策變數**：x[i] ∈ {0,1} (裝入/不裝入)。
目標**：最大化 Σ p[i]x[i]，滿足 Σ w[i]x[i] ≤ c。

三種基本貪婪策略與反例

策略	排序鍵值	反例 (n=3, c=30)	貪婪解	最優解	差距
最大價值優先	`p[i]` 遞減	w=[100,10,10], p=[20,15,15], c=105	x=[1,0,0] (值 20)	x=[0,1,1] (值 30)	33%
最小重量優先	`w[i]` 遞增	w=[10,20], p=[5,100], c=25	x=[1,0] (值 5)	x=[0,1] (值 100)	95%
最高價值密度優先	`p[i]/w[i]` 遞減	w=[20,15,15], p=[40,25,25], c=30	x=[1,0,0] (值 40)	x=[0,1,1] (值 50)	20%

結論**：0/1 背包**不具備貪婪選擇性質**，單純貪婪法不可靠。

k-最優啟發式演算法

核心思想**：枚舉所有大小 ≤ k 的物品子集作為「種子」，對每個種子，將其放入背包 (若可行)，剩餘容量用**價值密度貪婪**填滿。取所有種子產生解中的最優者。

演算法步驟

輸入 n, w[], p[], c, k。
生成所有 Σ_{i=0}^k C(n,i) 個子集 (種子)。
對每個種子 S：
- 若 Σ_{i∈S} w[i] > c → 捨棄。
- 否則：固定 x[i]=1 (i∈S)，剩餘物品按 p/w 遞減貪婪填入。
回傳所有可行種子產生解中的最大值解。

範例演示 (n=4, w=[2,4,6,7], p=[6,10,12,13], c=11)

密度排序**：物品 1(3.0), 2(2.5), 3(2.0), 4(1.86)。

k	枚舉種子	最優解	值	誤差界
0	{}	x=[1,1,0,0]	16	100%
1	{1},{2},{3},{4}	x=[1,0,0,1] (種子 {4})	19	50%
2	所有 2-組合	x=[0,1,0,1] (種子 {2,4})	23	33.3%

最優解 (窮舉)**：x=[0,1,0,1] 值 23，k=2 即達到最優。

理論誤差界證明大綱

設 OPT 為最優解，G_k 為 k-最優解。
考慮 OPT 中價值最高的 k+1 個項目，至少有一個不在 G_k 的種子中 (鴿巢原理)。透過交換論證可證明：
G_k ≥ (k/(k+1)) * OPT → 相對誤差 ≤ 1/(k+1) = 100/(k+1)%。

複雜度分析

種子數量：O(n^k) (固定 k 視為常數)。
每種子貪婪填滿：O(n log n) (排序) 或 O(n) (預排序)。
總時間：O(n^{k+1})。
實際觀察**：隨機實例中 k=1,2 往往已極接近最優，執行時間遠小於理論上界。

完整 C++ 實作框架

struct Item { int w, p, idx; double density; };

double KnapsackKOpt(const vector<Item> &items, int c, int k, vector<int> &best_x) {
    int n = items.size();
    vector<Item> sorted = items;
    sort(sorted.begin(), sorted.end(), [](auto &a, auto &b){ return a.density > b.density; });

    double best_val = 0;
    // 枚舉所有大小 <= k 的子集 (位元掩碼法，n≤20 適合)
    for (int mask = 0; mask < (1< k) continue;
        int weight = 0; double val = 0;
        vector<int> x(n, 0);
        bool feasible = true;
        // 固定種子項目
        for (int i = 0; i < n; ++i) if (mask & (1< c) { feasible = false; break; }
        }
        if (!feasible) continue;
        // 貪婪填滿剩餘
        for (int i = 0; i < n; ++i) if (!(mask & (1< best_val) { best_val = val; best_x = x; }
    }
    return best_val;
}