# 小背包問題：帶有示例的貪婪算法 > 原文： [https://www.guru99.com/fractional-knapsack-problem-greedy.html](https://www.guru99.com/fractional-knapsack-problem-greedy.html) ## 什么是貪婪策略？ 貪婪算法類似于動態編程算法，通常用于解決最佳問題（根據特定標準找到問題的最佳解決方案）。 貪婪算法執行最佳局部選擇，希望這些選擇將導致要解決的問題的最佳全局解決方案。 貪婪算法的設置通常不太難，快速（時間復雜度通常是線性函數或非常是二階函數）。 此外，這些程序調試起來并不難，并且占用的內存更少。 但是結果并不總是最佳的解決方案。 貪婪策略通常用于通過構建選項 A 來解決組合優化問題。通過選擇 A 的每個組件 Ai 直到完成（足夠 n 個組件）來構造選項 A。 對于每個 Ai，可以最佳地選擇 Ai。 這樣，在最后一步，您可能沒有其他選擇，只能接受最后剩余的值。 貪婪的決定有兩個關鍵組成部分： 1. 貪婪的選擇方式。 您可以選擇當前最合適的解決方案，然后解決最后一次選擇所引起的子問題。 貪婪算法的選擇可以取決于先前的選擇。 但這不能取決于將來的選擇或子問題的解決方案。 該算法以循環選擇的方式發展，同時將給定問題縮小為較小的子問題。 2. 最佳子結構。 如果此問題的最佳解決方案包含其子問題的最佳解決方案，則可以為該問題執行最佳子結構。 貪婪算法具有五個組成部分： 1. 一組候選人，從中可以創建解決方案。 2. 選擇功能，用于選擇要添加到解決方案中的最佳候選者。 3. 可行函數用于確定是否可以使用候選對象來構建解決方案。 4. 一個目標函數，用于確定解決方案或不完整解決方案的價值。 5. 評估功能，指示何時找到完整的解決方案。 在本教程中，您將學習 * [什么是貪婪策略？](#1) * [貪婪一號的想法](#2) * [貪婪二的構想](#3) * [貪婪三的想法](#4) * [貪婪三的 Java 代碼](#5) * [貪婪三的 Python3 代碼](#6) * [貪婪三的 C＃代碼](#7) * [貪婪三的反例](#8) ## 貪婪的想法 有了第一個想法，您就可以執行“貪婪的一號”的以下步驟： * 按值的非遞增順序排序。 * 反過來考慮訂購的包裹，如果背包的剩余容量足以容納背包，則將考慮的包裹放入背包（這意味著已放入背包的包裹的總重量和考慮的包裹的重量不超過 背包的容量）。 但是，這種貪婪算法并不總是能提供最佳解決方案。 這里有一個反例： * 問題的參數為：n = 3; M = 19。 * 軟件包：{i = 1; W [i] = 14； V [i] = 20}; {i = 2; W [i] = 6； V [i] = 16}; {i = 3; W [i] = 10； V [i] = 8} **->** 物有所值，但重量也很大。 * 該算法將選擇總值為 20 的程序包 1，而選擇總值為 24 的問題的最佳解決方案（程序包 2，程序包 3）。 ## 貪婪二的想法 有了第二個想法，您可以執行“貪婪之二”的以下步驟： * 按權重的非降序排序。 * 反過來考慮訂購的包裹，如果背包的剩余容量足以容納背包，則將考慮的包裹放入背包（這意味著已放入背包的包裹的總重量和考慮的包裹的重量不超過 背包的容量）。 However, this greedy algorithm does not always give the optimal solution. Here you have a counter-example: * 問題的參數為：n = 3; M = 11。 * 軟件包：{i = 1; W [i] = 5； V [i] = 10}; {i = 2; W [i] = 6； V [i] = 16}; {i = 3; W [i] = 10； V [i] = 28} **->** 重量輕，但該值也很輕。 * 該算法將選擇（包 1，包 2）的總值為 26，而問題的最佳解決方案是（包 3）總值為 28。 ## 貪婪三的想法 有了第三個想法，您就可以完成“貪婪三號”的以下步驟。 實際上，這是使用最廣泛的算法。 * 按照不增加單位成本  的值的順序對包進行排序。 你有：  * 反過來考慮訂購的包裹，如果背包的剩余容量足以容納背包，則將考慮的包裹放入背包（這意味著已放入背包的包裹的總重量和考慮的包裹的重量不超過 背包的容量）。 **想法**：這個問題的貪婪想法是計算每個  的  比。 然后按降序對這些比率進行排序。 您將選擇最高的  包裝，背包的容量可以容納該包裝（剩余> w _i ）。 每次將包裹放入背包時，都會減少背包的容量。 選擇包的方式： * 考慮一下單位成本陣列。 您可以根據降低的單位成本選擇包裝。  * 假設您找到了一個部分解：（x ₁ ，...，x _i ）。 * 獲得背包的值：  * 對應于已放入背包的包裹的重量：  * 因此，背包的剩余重量限制為：  ### 算法步驟 您會看到這是找到最大數量的問題。 軟件包列表按單位成本的降序排序，以考慮分支。 * **步驟 1** ：節點根代表背包的初始狀態，尚未選擇任何包。 * TotalValue = 0。 * 根節點的上限 UpperBound = M *最大單位成本。 * **步驟 2** ：節點根將具有子節點，該子節點對應于選擇具有最大單位成本的軟件包的能力。 對于每個節點，您將重新計算參數： * TotalValue = TotalValue（舊）+選定包的數量*每個包的值。 * M = M（舊）–選擇的包裹數*每個包裹的重量。 * UpperBound = TotalValue + M（新）*接下來要考慮的包裝的單位成本。 * **步驟 3** ：在子節點中，您將優先考慮具有較大上限的節點的分支。 該節點的子級對應于選擇具有較大單位成本的下一個軟件包的能力。 對于每個節點，必須根據步驟 2 中提到的公式重新計算參數 TotalValue，M，UpperBound。 * **步驟 4** ：重復第 3 步，并注意：對于具有上限的節點小于或等于找到的選項的臨時最大成本，您不再需要為該節點分支。 * **步驟 5** ：如果所有節點都被分支或切斷，則最昂貴的選擇是尋找的一種。 該算法的偽代碼： ``` Fractional Knapsack (Array W, Array V, int M) 1\. for i <- 1 to size (V) 2\. calculate cost[i] <- V[i] / W[i] 3\. Sort-Descending (cost) 4\. i ← 1 5\. while (i <= size(V)) 6\. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9\. if W[i] > M 10\. i ← i+1 ``` 該算法的復雜性： * 如果使用簡單的排序算法（選擇，冒泡…），則整個問題的復雜度為 O（n2）。 * 如果使用快速排序或合并排序，則整個問題的復雜度為 O（nlogn）。 ## 貪婪三的 Java 代碼 * 首先，定義類 KnapsackPackage。 該類的屬性是：每個包裝的重量，價值和相應的成本。 此類的屬性成本用于主算法中的排序任務。 每個成本的價值是每個包裝的  比率。 ``` public class KnapsackPackage { private double weight; private double value; private Double cost; public KnapsackPackage(double weight, double value) { super(); this.weight = weight; this.value = value; this.cost = new Double(value / weight); } public double getWeight() { return weight; } public double getValue() { return value; } public Double getCost() { return cost; } } ``` * 然后，您創建一個函數來執行算法貪婪三。 ``` public void knapsackGreProc(int W[], int V[], int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int i = 0; i < n; i ++) { packs[i] = new KnapsackPackage(W[i], V[i]); } Arrays.sort(packs, new Comparator<KnapsackPackage>() { @Override public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) { return kPackB.getCost().compareTo(kPackA.getCost()); } }); int remain = M; double result = 0d; int i = 0; boolean stopProc = false; while (!stopProc) { if (packs[i].getWeight() <= remain) { remain -= packs[i].getWeight(); result += packs[i].getValue(); System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue()); } if (packs[i].getWeight() > remain) { i ++; } if (i == n) { stopProc = true; } } System.out.println("Max Value:\t" + result); } ``` <figure style="margin-left: auto;margin-right: auto;">  Function knapsackGreProc() in Java **代碼說明**： 1. 初始化每個背包包裝的重量和價值。 2. 按成本降序排列背包包裝。 3. 如果選擇包裝 i。 4. 如果選擇包裹數，我就足夠了。 5. 瀏覽所有軟件包時停止。 在本教程中，您有兩個示例。 這是運行上述程序的 Java 代碼，其中包含兩個示例： ``` public void run() { /* * Pack and Weight - Value */ //int W[] = new int[]{15, 10, 2, 4}; int W[] = new int[]{12, 2, 1, 1, 4}; //int V[] = new int[]{30, 25, 2, 6}; int V[] = new int[]{4, 2, 1, 2, 10}; /* * Max Weight */ //int M = 37; int M = 15; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); } ``` 您有輸出： * 第一個例子： ``` Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0 ``` * 第二個例子： ``` Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0 ``` 分析第一個示例： * 問題的參數為：n = 4; M = 37。 * 軟件包：{i = 1; W [i] = 15； V [i] = 30; 費用= 2.0}； {i = 2; W [i] = 10； V [i] = 25; 費用= 2.5}； {i = 3; W [i] = 2; V [i] = 4； 費用= 1.0}； {i = 4; W [i] = 4； V [i] = 6； 費用= 1.5}。 * 您按不增加單位成本價值的順序對包裹進行排序。 您有：{i = 2} **->** {i = 1} **->** {i = 4} **->** {i = 3}。 適用于第一個示例的算法的步驟： * 定義 x1，x2，x3，x4 是每個選定軟件包的編號，對應于軟件包{i = 2} **->** {i = 1} **->** { i = 4} **->** {i = 3}。 * 節點根目錄 N 表示您尚未選擇任何程序包的狀態。 然后： * TotalValue = 0。 * M = 37（建議值）。 * UpperBound = 37 * 2.5 = 92.5，其中 37 是 M，2.5 是包裝{i = 2}的單位成本。 * 對于包{i = 2}，您有 4 種可能性：選擇 3 個包{i = 2}（x1 = 3）； 選擇 2 個軟件包{i = 2}（x1 = 2）； 選擇 1 個程序包{i = 2}（x1 = 1），而不選擇程序包{i = 2}（x1 = 0）。 根據這 4 種可能性，您將根節點 N 分支為 4 個子節點 N [1]，N [2]，N [3]和 N [4]。 * 對于子節點 N1，您具有： * TotalValue = 0 + 3 * 25 = 75，其中 3 是所選軟件包{i = 2}的數量，而 25 是每個軟件包{i = 2}的值。 * M = 37 – 3 * 10 = 7，其中 37 是背包的初始數量，3 是包裹的數量{i = 2}，10 是每個包裹的重量{i = 2}。 * UpperBound = 75 + 7 * 2 = 89，其中 75 是 TotalValue，7 是背包的剩余重量，2 是包裹的單位成本{i = 1}。 * 同樣，您可以計算節點 N [2]，N [3]和 N [4]的參數，其中上限分別為 84、79 和 74。 * 在節點 N [1]，N [2]，N [3]和 N [4]中，節點 N [1]具有最大的上限，因此您將首先分支節點 N [1]，希望會有一個 從這個方向好計劃。 * 在節點 N [1]中，只有一個子節點 N [1-1]對應于 x2 = 0（由于背包的剩余重量為 7，而每個包裹{i = 1}的重量為 15） 。 確定 N [1-1]按鈕的參數后，N [1-1]的上限為 85.5。 * 您繼續分支節點 N [1-1]。 節點 N [1-1]有 2 個子節點 N [1-1-1]和 N [1-1-2]，分別對應 x3 = 1 和 x3 =0。確定了這兩個節點的參數后，您會看到 N [1-1-1]的 UpperBoundary 為 84，而 N [1-1-2]的 UpperBoundary 為 82，因此您繼續分支節點 N [1-1-1]。 * 節點 N [1-1-1]有兩個子節點 N [1-1-1-1]和 N [1-1-1-2]，分別對應 x4 = 1 和 x4 =0。這是兩個葉節點 （代表該選項），因為已為每個節點選擇了軟件包數量。 其中節點 N [1-1-1-1]表示選項 x1 = 3，x2 = 0，x3 = 1 和 x4 = 1 對于 83，而節點 N [1-1-1-2]表示選項 x1 = 3，x2 = 0，x3 = 1，x4 = 01，位于 81。因此，此處的臨時最大值為 83。 * 回到節點 N [1-1-2]，您會看到 N [1-1-2]的上限是 82 < 83，因此您修剪了節點 N [1-1-2]。 * 回到節點 N2，您會看到 N2 的上限是 84 > 83，因此您繼續分支節點 N2。 節點 N2 有兩個子 N [2-1]和 N [2-2]，分別對應 x2 = 1 和 x2 =0。在計算了 N [2-1]和 N [2-2]的參數后，您會看到 N [2-1]的上限為 N [2-2]的上限為 75.25。 這些值都不大于 83，因此兩個節點都被修剪。 * 最后，節點 N3 和 N4 也被修剪。 * 因此，樹上的所有節點都被分支或修剪，因此最好的臨時解決方案是尋找該解決方案。 因此，您需要選擇 3 個包裹{i = 2}，1 個包裹{i = 4}和一個包裹{i = 3}，總價值為 83，總重量為 36。 與第二個示例的分析相同，您得到的結果是：選擇程序包 4（3 次）和程序包 5（3 次）。 ## 貪婪三的 Python3 代碼 * 首先，定義類 KnapsackPackage。 ``` class KnapsackPackage(object): """ Knapsack Package Data Class """ def __init__(self, weight, value): self.weight = weight self.value = value self.cost = value / weight def __lt__(self, other): return self.cost < other.cost ``` * 然后，您創建一個函數來執行算法貪婪三。 ``` class FractionalKnapsack(object): def __init__(self): def knapsackGreProc(self, W, V, M, n): packs = [] for i in range(n): packs.append(KnapsackPackage(W[i], V[i])) packs.sort(reverse = True) remain = M result = 0 i = 0 stopProc = False while (stopProc != True): if (packs[i].weight <= remain): remain -= packs[i].weight; result += packs[i].value; print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value) if (packs[i].weight > remain): i += 1 if (i == n): stopProc = True print("Max Value:\t", result) ``` <figure style="margin-left: auto;margin-right: auto;">  Function knapsackGreProc() in Python **Explanation of code:** 1. 初始化每個背包包裝的重量和價值。 2. 按成本降序排列背包包裝。 3. 如果選擇包裝 i。 4. 如果選擇包裹數，我就足夠了。 5. 瀏覽所有軟件包時停止。 這是使用第一個示例運行上述程序的 Python3 代碼： ``` if __name__ == "__main__": W = [15, 10, 2, 4] V = [30, 25, 2, 6] M = 37 n = 4 proc = FractionalKnapsack() proc.knapsackGreProc(W, V, M, n) ``` You have the output: ``` Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83 ``` ## 貪婪三的 C＃代碼 * 首先，定義類 KnapsackPackage。 ``` using System; namespace KnapsackProblem { public class KnapsackPackage { private double weight; private double value; private double cost; public KnapsackPackage(double weight, double value) { this.weight = weight; this.value = value; this.cost = (double) value / weight; } public double Weight { get { return weight; } } public double Value { get { return value; } } public double Cost { get { return cost; } } } } ``` * 然后，您創建一個函數來執行算法貪婪三。 ``` using System; namespace KnapsackProblem { public class FractionalKnapsack { public FractionalKnapsack() { } public void KnapsackGreProc(int[] W, int[] V, int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int k = 0; k < n; k++) packs[k] = new KnapsackPackage(W[k], V[k]); Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>( (kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost))); double remain = M; double result = 0d; int i = 0; bool stopProc = false; while (!stopProc) { if (packs[i].Weight <= remain) { remain -= packs[i].Weight; result += packs[i].Value; Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value); } if (packs[i].Weight > remain) { i++; } if (i == n) { stopProc = true; } } Console.WriteLine("Max Value:\t" + result); } } } ``` <figure style="margin-left: auto;margin-right: auto;">  Function KnapsackGreProc() in C# **Explanation of code:** 1. 初始化每個背包包裝的重量和價值。 2. 按成本降序排列背包包裝。 3. 如果選擇包裝 i。 4. 如果選擇包裹數，我就足夠了。 5. 瀏覽所有軟件包時停止。 這是使用第一個示例運行上述程序的 C＃代碼： ``` public void run() { /* * Pack and Weight - Value */ int[] W = new int[]{15, 10, 2, 4}; //int[] W = new int[] { 12, 2, 1, 1, 4 }; int[] V = new int[]{30, 25, 2, 6}; //int[] V = new int[] { 4, 2, 1, 2, 10 }; /* * Max Weight */ int M = 37; //int M = 15; int n = V.Length; /* * Run the algorithm */ KnapsackGreProc(W, V, M, n); } ``` You have the output: ``` Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83 ``` ## 貪婪三的反例 貪婪三號算法可以快速求解，并且在某些情況下也可以是最優的。 但是，在某些特殊情況下，它不能提供最佳解決方案。 這里有一個反例： * 問題的參數為：n = 3; M = 10。 * 軟件包：{i = 1; W [i] = 7; V [i] = 9; 費用= 9/7}； {i = 2; W [i] = 6； V [i] = 6； 費用= 1}； {i = 3; W [i] = 4； V [i] = 4； 費用= 1}。 * 該算法將選擇（包 1）的總值為 9，而該問題的最佳解決方案是（包 2，包 3）的總值為 10。 這是帶有反示例的運行上述程序的 Java 代碼： ``` public void run() { /* * Pack and Weight - Value */ int W[] = new int[]{7, 6, 4}; int V[] = new int[]{9, 6, 4}; /* * Max Weight */ int M = 10; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); } ``` 結果如下： ``` Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0 ``` 這就是分數背包問題。