我正在通過 OpenCourseWare 上的 MIT6.0002（https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science -fall-2016/assignments/），我被問題集 1 的 B 部分難住了。這個問題是作為背包問題的一個版本提出的，表述如下：[奧克夫婦發現了一群能下不同重量金蛋的鵝]他們希望在旅途中攜帶盡可能少的蛋，因為他們的船上沒有太多空間。他們已經詳細記錄了鵝可以在給定群中產下的所有雞蛋的重量以及他們的船可以承載多少重量。在 dp_make_weight 中實現一個動態規劃算法來找到為某艘船制造給定重量所需的最小雞蛋數量。結果應該是一個整數，表示從給定的鵝群中獲得給定重量所需的最小蛋數。您的算法不需要返回雞蛋的重量，只需要返回最小數量的雞蛋。假設： - 不同鵝之間的所有雞蛋重量都是唯一的，但是一只給定的鵝總是會產下相同大小的雞蛋——Aucks 可以等待鵝產下所需數量的雞蛋[即每種大小的雞蛋都有無限的供應]。- 總有 1 號的雞蛋可用該問題還指出解決方案必須使用動態規劃。我已經編寫了一個解決方案（在 Python 中），我認為它找到了最佳解決方案，但它不使用動態編程，我無法理解動態編程是如何適用的。還建議解決方案應使用遞歸。任何人都可以向我解釋在這種情況下使用記憶的好處是什么，以及通過實施遞歸解決方案我會得到什么？（如果我的問題太含糊，或者解決方案對文字來說太明顯，我深表歉意；我是編程和這個網站的相對初學者）。
1 回答
米琪卡哇伊
TA貢獻1998條經驗 獲得超6個贊
這里的問題是典型的 DP 情況，貪婪有時可以給出最優解，但有時不能。
這個問題的情況類似于經典的 DP 問題硬幣找零，在給定目標值的情況下，我們希望找到最少數量的不同價值硬幣來找零。在美國等一些國家（使用價值 1、5、10、25、50、100 的硬幣）可用的面額是這樣的，最好是貪婪地選擇最大的硬幣，直到價值低于它，然后繼續下一個硬幣。但是對于其他面額集合，如 1、3、4，反復貪婪地選擇最大值會產生次優結果。
同樣，您的解決方案適用于某些蛋重，但對其他蛋重無效。如果我們選擇雞蛋的權重為 1、6、9，并給出目標權重 14，算法會立即選擇 9，然后無法在 6 上取得進展。此時，它會吞下一堆 1，最終認為是 6是最小的解決方案。但這顯然是錯誤的：如果我們聰明地忽略 9 并先選擇兩個 6，那么我們可以只用 4 個雞蛋達到所需的重量。
這表明我們必須考慮這樣一個事實，即在任何決策點，采用我們的任何面額都可能最終導致我們獲得全局最優解。但我們暫時無法知道。所以，我們每一步都嘗試每一個面額。這非常有利于遞歸，可以這樣寫：
def dp_make_weight(egg_weights, target_weight):
least_taken = float("inf")
if target_weight == 0:
return 0
elif target_weight > 0:
for weight in egg_weights:
sub_result = dp_make_weight(egg_weights, target_weight - weight)
least_taken = min(least_taken, sub_result)
return least_taken + 1
if __name__ == "__main__":
print(dp_make_weight((1, 6, 9), 14))
對于每個調用，我們有 3 種可能性：
基本情況
target_weight < 0：返回一些東西以表明不可能有解決方案（為了方便起見，我使用了無窮大）。基本案例
target_weight == 0：我們找到了一個候選解決方案。返回 0 表示此處未采取任何步驟，并為調用者提供一個要遞增的基值。遞歸案例
target_weight > 0：嘗試egg_weight通過從總數中減去每個可用的值并遞歸地探索根植于新狀態的路徑。在探索了當前狀態的所有可能結果之后，選擇用最少的步驟達到目標的結果。加 1 計數當前步驟的取蛋并返回。
到目前為止，我們已經看到貪婪的解決方案是不正確的以及如何修復它，但還沒有激發動態編程或記憶。DP和memoization是純粹的優化概念，所以你可以在找到正確的解決方案并需要加速之后添加它們。上述解決方案的時間復雜度是指數級的：對于每個調用，我們都必須產生len(egg_weights)遞歸調用。
有很多資源可以解釋 DP 和記憶化，我相信你的課程涵蓋了它，但簡而言之，我們上面顯示的遞歸解決方案通過采用不同的遞歸路徑一遍又一遍地重新計算相同的結果，最終導致給出相同的值為target_weight. 如果我們保留一份備忘錄（字典），將每次調用的結果存儲在內存中，那么每當我們再次遇到調用時，我們都可以查找它的結果，而不是從頭開始重新計算它。
def dp_make_weight(egg_weights, target_weight, memo={}):
least_taken = float("inf")
if target_weight == 0:
return 0
elif target_weight in memo:
return memo[target_weight]
elif target_weight > 0:
for weight in egg_weights:
sub_result = dp_make_weight(egg_weights, target_weight - weight)
least_taken = min(least_taken, sub_result)
memo[target_weight] = least_taken + 1
return least_taken + 1
if __name__ == "__main__":
print(dp_make_weight((1, 6, 9, 12, 13, 15), 724)) # => 49
由于我們使用的是 Python，因此“Pythonic”的做法可能是裝飾函數。事實上，有一個內置的 memoizer 叫做lru_cache，所以回到我們原來的函數沒有任何 memoization，我們可以用兩行代碼添加 memoization（緩存）：
from functools import lru_cache
@lru_cache
def dp_make_weight(egg_weights, target_weight):
# ... same code as the top example ...
使用裝飾器進行記憶的缺點是調用堆棧的大小與包裝器的大小成正比，因此它會增加爆棧的可能性。這是迭代編寫 DP 算法的一個動機，自下而上（即，從解決方案基本案例開始，建立這些小解決方案的表格，直到您能夠構建全局解決方案），這可能是一個很好的練習如果您正在尋找另一個角度，這個問題。
添加回答
舉報
0/150
提交
取消