C++分?jǐn)?shù)背包問(wèn)題

圖 15-3   分?jǐn)?shù)背包問(wèn)題的示例數(shù)據(jù)

分?jǐn)?shù)背包和 0-1 背包整體上非常相似，狀態(tài)包含當(dāng)前物品 $i$ 和容量 $c$ ，目標(biāo)是求不超過(guò)背包容量下的最大價(jià)值。

不同點(diǎn)在于，本題允許只選擇物品的一部分。如圖 15-4 所示，我們可以對(duì)物品任意地進(jìn)行切分，并按照重量比例來(lái)計(jì)算物品價(jià)值。

1. 對(duì)于物品 $i$ ，它在單位重量下的價(jià)值為 $val[i?1]/wgt[i?1]$ ，簡(jiǎn)稱為單位價(jià)值。
2. 假設(shè)放入一部分物品 $i$ ，重量為 $w$ ，則背包增加的價(jià)值為 $w\times val[i?1]/wgt[i?1]$ 。

圖 15-4   物品在單位重量下的價(jià)值

1.   貪心策略確定

最大化背包內(nèi)物品總價(jià)值，本質(zhì)上是要最大化單位重量下的物品價(jià)值。由此便可推出圖 15-5 所示的貪心策略。

1. 將物品按照單位價(jià)值從高到低進(jìn)行排序。
2. 遍歷所有物品，每輪貪心地選擇單位價(jià)值最高的物品。
3. 若剩余背包容量不足，則使用當(dāng)前物品的一部分填滿背包即可。

圖 15-5   分?jǐn)?shù)背包的貪心策略

2.   代碼實(shí)現(xiàn)

我們建立了一個(gè)物品類 Item ，以便將物品按照單位價(jià)值進(jìn)行排序。循環(huán)進(jìn)行貪心選擇，當(dāng)背包已滿時(shí)跳出并返回解。

fractional_knapsack.cpp

/* 物品 */
class Item {
  public:
    int w; // 物品重量
    int v; // 物品價(jià)值

    Item(int w, int v) : w(w), v(v) {
    }
};

/* 分?jǐn)?shù)背包：貪心 */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
    // 創(chuàng)建物品列表，包含兩個(gè)屬性：重量、價(jià)值
    vector<Item> items;
    for (int i = 0; i < wgt.size(); i++) {
        items.push_back(Item(wgt[i], val[i]));
    }
    // 按照單位價(jià)值 item.v / item.w 從高到低進(jìn)行排序
    sort(items.begin(), items.end(), [](Item &a, Item &b) { return (double)a.v / a.w > (double)b.v / b.w; });
    // 循環(huán)貪心選擇
    double res = 0;
    for (auto &item : items) {
        if (item.w <= cap) {
            // 若剩余容量充足，則將當(dāng)前物品整個(gè)裝進(jìn)背包
            res += item.v;
            cap -= item.w;
        } else {
            // 若剩余容量不足，則將當(dāng)前物品的一部分裝進(jìn)背包
            res += (double)item.v / item.w * cap;
            // 已無(wú)剩余容量，因此跳出循環(huán)
            break;
        }
    }
    return res;
}

最差情況下，需要遍歷整個(gè)物品列表，因此時(shí)間復(fù)雜度為 $O(n)$ ，其中 $n$ 為物品數(shù)量。

由于初始化了一個(gè) Item 對(duì)象列表，因此空間復(fù)雜度為 $O(n)$ 。

3.   正確性證明

采用反證法。假設(shè)物品 $x$ 是單位價(jià)值最高的物品，使用某算法求得最大價(jià)值為 res ，但該解中不包含物品 $x$ 。

現(xiàn)在從背包中拿出單位重量的任意物品，并替換為單位重量的物品 $x$ 。由于物品 $x$ 的單位價(jià)值最高，因此替換后的總價(jià)值一定大于 res 。這與 res 是最優(yōu)解矛盾，說(shuō)明最優(yōu)解中必須包含物品 $x$ 。

對(duì)于該解中的其他物品，我們也可以構(gòu)建出上述矛盾。總而言之，單位價(jià)值更大的物品總是更優(yōu)選擇，這說(shuō)明貪心策略是有效的。

如圖 15-6 所示，如果將物品重量和物品單位價(jià)值分別看作一個(gè) 2D 圖表的橫軸和縱軸，則分?jǐn)?shù)背包問(wèn)題可被轉(zhuǎn)化為“求在有限橫軸區(qū)間下的最大圍成面積”。這個(gè)類比可以幫助我們從幾何角度理解貪心策略的有效性。

圖 15-6   分?jǐn)?shù)背包問(wèn)題的幾何表示