C++分數(shù)背包問題

圖 15-3   分數(shù)背包問題的示例數(shù)據(jù)

分數(shù)背包和 0-1 背包整體上非常相似，狀態(tài)包含當前物品 $i$ 和容量 $c$ ，目標是求不超過背包容量下的最大價值。

不同點在于，本題允許只選擇物品的一部分。如圖 15-4 所示，我們可以對物品任意地進行切分，并按照重量比例來計算物品價值。

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

圖 15-4   物品在單位重量下的價值

1.   貪心策略確定

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

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

圖 15-5   分數(shù)背包的貪心策略

2.   代碼實現(xiàn)

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

fractional_knapsack.cpp

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

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

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

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

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

3.   正確性證明

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

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

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

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

圖 15-6   分數(shù)背包問題的幾何表示