我需要幫助證明演算法具有貪心選擇屬性和最優子結構。
問題的背景：
考慮一個公司擁有n通過高速公路連接的加油站的問題。每個加油站g_i的氣罐供應有限。由于公司不知道哪個加油站訪問量最大，他們希望所有加油站都擁有相同數量的汽油。
因此，他們租用了一輛加油卡車在卡車的加油站之間運輸汽油。但是，卡車每行駛一公里也會消耗 1 個汽油罐。
g_bar
你的任務是幫助連鎖店計算他們在所有加油站可以擁有的最大數量的氣罐。
考慮這個例子：這里我們有 g = (20, 40, 80, 10, 20) 和 p = (0, 5, 13, 33, 36)（以公里為單位）。為了將一個氣罐從 3 號站發送到 4 號站，我們需要在卡車上放 41 個氣罐，因為加油車在到達目的地之前會消耗 40 個氣罐（要發送兩個氣罐，我們需要放 42 個氣罐）在卡車上）。該示例的最佳g_bar值是 21，可以按如下方式實作：
2 號站向 1 號站發送 11 個氣罐。一個氣罐到達，10 個氣罐在途中消耗。
3 號站向 4 號站發送 59 個氣罐。19 個到達，40 個在途中消耗。
4 號站現在有 29 個氣罐，向 5 號站發送了 8 個。其中兩個到達，六個在途中消耗。
氣罐的最終分布是：（21、29、21、21、22）。
給定一個整數 g_bar。g_bar確定是否有可能在每個加油站中至少獲得 氣罐。
g_bar為了使貪心選擇屬性和最優子結構對決策問題有意義，如果存在這樣的解決方案，您可以將最優解決方案定義為每個加油站中至少有氣罐的解決方案；否則，任何解都是最優解。
輸入：位置p_i和氣體-可以供應g_i of每個酒吧。這g_i是 position 柱的供應量p_i。您可以假設這些位置是按排序順序排列的——即p_1 < p_2 < . . . < p_n。
輸出：最大量g_bar，使得每個加油站至少可以g_bar在卡車在加油站之間轉移氣罐后有一個氣罐供應。
我如何為此證明貪婪選擇和最優子結構？
uj5u.com熱心網友回復：
讓我們定義一個最佳解決方案：每個站點至少有每個站點中的X氣罐（X= g_bar）。
證明貪心財產
讓我們假設我們的解決方案是次優的。必須存在一個站i，這樣gas[i]< X。根據我們的演算法，我們X - gas[i]從站借i 1（這是一個有效的移動，因為我們已經找到了一個解決方案）。現在站i有gas = X。這與原來的假設相矛盾，即必須存在i這樣的站gas[i]< X，這意味著我們的解決方案不是次優的。因此，我們證明了最優性。
證明最優子結構
假設我們有一個大小為 的站點的子集N'，并且我們的解決方案是次優的。同樣，如果解決方案是次優的，則必須存在一個i滿足gas[i]<的站X。您可以再次使用貪心證明來證明我們的解決方案不是次優的。由于我們對每個任意子集都有最優解，我們證明我們有最優子結構。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446409.html