動態規劃 - 尋找最大利潤

Question

我是新來的動態規劃。所以，我想找到最大的利潤。我不認爲我在做什麼是正確的。我不明白k轉換是什麼。在給定的例子中有3種貨幣，因此有3種貨幣兌換。有人可以給我更多關於如何解決這個問題的想法嗎？

Answer 1

首先，讓我們想想有多少貨幣交易有。如果您有三種貨幣（我們姑且稱之爲英鎊，法郎和馬克）你有六種可能的種貨幣交易：磅標記，標記來斤，英鎊瑞郎，瑞郎英鎊，法郎標記，與標記法郎。

但你的問題而言，當他們說你的K幣交易，他們的意思是，你可以開始與一些貨幣，使ķ貨幣交易的序列。你的工作是找出哪些k次交易會帶來最大的利潤。例如，如果您有三種貨幣，但k = 1，並且您被告知以磅開始，那麼您的任務很簡單：確定英鎊兌法郎是更好還是英鎊兌美元更好。若k = 2，你有更多的選擇，等

它可能會以爲這是一個加權有向圖，其中貨幣是節點樂於助人，和弧由匯率加權。然後，您可以考慮通過圖表找到最有利可圖的路徑問題，長度爲k，從節點i開始。

思考這種方式也將顯示你在表達的問題，這應該看起來像沿着圖形的路徑，而不是你擁有什麼。您也可以考慮使用一些對數性質，將其從有關乘法的問題轉化爲有關加法的問題。

最後，圖形結構上的動態編程通常包括從長度爲n的解決方案中構建一個長度爲n + 1的解決方案，因此您應該先考慮最小可能的問題，以及它如何與第二個問題相關最小的問題，等等。