<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 小背包問題:帶有示例的貪婪算法 > 原文: [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。 ## 貪婪三的想法 有了第三個想法,您就可以完成“貪婪三號”的以下步驟。 實際上,這是使用最廣泛的算法。 * 按照不增加單位成本 ![](https://img.kancloud.cn/5b/4b/5b4b5c4372f1a9b414b43b7966c51ee7_37x51.png) 的值的順序對包進行排序。 你有: ![](https://img.kancloud.cn/45/59/455928ffe8e9ce3da99d443c6571bddf_259x74.png) * 反過來考慮訂購的包裹,如果背包的剩余容量足以容納背包,則將考慮的包裹放入背包(這意味著已放入背包的包裹的總重量和考慮的包裹的重量不超過 背包的容量)。 **想法**:這個問題的貪婪想法是計算每個 ![](https://img.kancloud.cn/5b/4b/5b4b5c4372f1a9b414b43b7966c51ee7_37x51.png) 的 ![](https://img.kancloud.cn/b2/ad/b2ad15fc0939961191a9137be487f1cb_79x47.png) 比。 然后按降序對這些比率進行排序。 您將選擇最高的 ![](https://img.kancloud.cn/5b/4b/5b4b5c4372f1a9b414b43b7966c51ee7_37x51.png) 包裝,背包的容量可以容納該包裝(剩余> w <sub>i</sub> )。 每次將包裹放入背包時,都會減少背包的容量。 選擇包的方式: * 考慮一下單位成本陣列。 您可以根據降低的單位成本選擇包裝。 ![](https://img.kancloud.cn/9a/e2/9ae229d834bbd602568acb36bcc4cf22_201x76.png) * 假設您找到了一個部分解:(x <sub>1</sub> ,...,x <sub>i</sub> )。 * 獲得背包的值: ![](https://img.kancloud.cn/9e/9b/9e9b2d42c3b02d51340fbfeee2115c97_474x97.png) * 對應于已放入背包的包裹的重量: ![](https://img.kancloud.cn/99/f4/99f4a21676dacd8b1f8718b2bce39699_526x103.png) * 因此,背包的剩余重量限制為: ![](https://img.kancloud.cn/64/67/646777b31a298ee66bf3f11d986fcf65_373x101.png) ### 算法步驟 您會看到這是找到最大數量的問題。 軟件包列表按單位成本的降序排序,以考慮分支。 * **步驟 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。 該類的屬性是:每個包裝的重量,價值和相應的成本。 此類的屬性成本用于主算法中的排序任務。 每個成本的價值是每個包裝的 ![](https://img.kancloud.cn/b2/ad/b2ad15fc0939961191a9137be487f1cb_79x47.png) 比率。 ``` 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;"> ![](https://img.kancloud.cn/70/bf/70bf893875203a20767354b9a47dfab7_960x619.png) 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;"> ![](https://img.kancloud.cn/b6/4c/b64c64febfbbbe526b5d92e5095a9531_753x521.png) 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;"> ![](https://img.kancloud.cn/ad/67/ad67a783a669cd0e72203e4a2cdeb214_868x620.png) 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 ``` 這就是分數背包問題。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看