一、背景介紹

給定𝑛個物品，第𝑖個物品的重量為𝑤𝑔𝑡[𝑖?1]、價值為𝑣𝑎𝑙[𝑖?1]，和一個容量為𝑐𝑎𝑝的 背包。每個物品只能選擇一次，但可以選擇物品的一部分，價值根據選擇的重量比例計算，問：在不超過背包容量下背包中物品的最大價值。

如下圖所示，我們可以對物品任意地進行切分，并按照重量 比例來計算物品價值。

1. 對于物品𝑖，它在單位重量下的價值為𝑣𝑎𝑙[𝑖?1]/𝑤𝑔𝑡[𝑖?1]，簡稱為單位價值。

2. 假設放入一部分物品𝑖，重量為𝑤，則背包增加的價值為𝑤×𝑣𝑎𝑙[𝑖?1]/𝑤𝑔𝑡[𝑖?1]。

二、具體實現

1. 貪心策略確定

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

1）將物品按照單位價值從高到低進行排序。

2）遍歷所有物品，每輪貪心地選擇單位價值最高的物品。

3）若剩余背包容量不足，則使用當前物品的一部分填滿背包即可。

2.代碼實現

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

class Item:"""物品"""def __init__(self, w: int, v: int):self.w = w  # 物品重量self.v = v  # 物品價值def fractional_knapsack(wgt: list[int], val: list[int], cap: int) -> int:"""分數背包：貪心"""# 創建物品列表，包含兩個屬性：重量、價值items = [Item(w, v) for w, v in zip(wgt, val)]# 按照單位價值 item.v / item.w 從高到低進行排序items.sort(key=lambda item: item.v / item.w, reverse=True)# 循環貪心選擇res = 0for item in items:if item.w <= cap:# 若剩余容量充足，則將當前物品整個裝進背包res += item.vcap -= item.welse:# 若剩余容量不足，則將當前物品的一部分裝進背包res += (item.v / item.w) * cap# 已無剩余容量，因此跳出循環breakreturn res"""Driver Code"""
if __name__ == "__main__":wgt = [10, 20, 30, 40, 50]val = [50, 120, 150, 210, 240]cap = 50n = len(wgt)# 貪心算法res = fractional_knapsack(wgt, val, cap)print(f"不超過背包容量的最大物品價值為 {res}")

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

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

三、正確性證明

采用反證法。

假設物品𝑥是單位價值最高的物品，使用某算法求得最大價值為res，但該解中不包含物品𝑥 。 現在從背包中拿出單位重量的任意物品，并替換為單位重量的物品𝑥。由于物品𝑥的單位價值最高，因此替 換后的總價值一定大于res。這與res是最優解矛盾，說明最優解中必須包含物品𝑥。 對于該解中的其他物品，我們也可以構建出上述矛盾。總而言之，單位價值更大的物品總是更優選擇，這說 明貪心策略是有效的。

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

?

?