找到最有利的貨幣兌換順序

Question

我正在從我的書中進行以下練習：

最短路徑算法可應用於貨幣交易。讓c1，c2，...。 。 。 ，cn是各種各樣的rencies;例如，c1可能是美元，c2磅和c3里拉。對於任何兩種貨幣ci和 cj，都存在匯率ri，j;這意味着你可以在 之間兌換一單位的貨幣單位，購買ri，j貨幣單位cj。這些匯率滿足條件裏，J·RJ，我< 1，因此，如果 你與貨幣詞的單位開始，它變成貨幣CJ，然後再轉換回貨幣 詞，你最終小於一個單位的貨幣ci（差額是交易的成本）。 （a）給出以下問題的有效算法：給定一組匯率的R I，J， 和兩種貨幣S和T，找到貨幣兌換的最有利序列 轉換貨幣s轉換貨幣噸。爲實現這一目標，您應該使用幣種 來表示費率，並用邊長爲實數的圖表進行匯率分析。

---

所以基本上我們想要做的是不是最小化，我們需要最大化利潤。因此我們需要找到從s到t的最長路徑。我們斷言存在從s到t的最短路徑。

我認爲解決這個問題是這樣的算法如下方式：

1. 取反所有的圖形
2. 運行的向無環圖的最短路徑算法的邊緣。

我相信這會工作，但我不知道。在谷歌，我發現一些解決方案，包括另一個步驟：將利率的乘法轉換爲使用對數的加法。我認爲這一步並不是必要的，但我仍然不確定。

Answer 1

不要試圖使用Google或StackOverflow來尋找解決方案，只需考慮一段時間。雖然許多問題可以通過從各種來源收集資源，信息和想法來解決，但有些問題不能。讓你的電腦進入睡眠狀態。去找個安靜的地方。想想看，直到你有了一個想法。在廢紙或白板上繪製樣本圖。試試看。看看它是否有效。如果它不考慮爲什麼不嘗試找到新的想法。如果確實如此，請嘗試考慮一個不適用的有效圖表。當你確信自己已經有了適用於所有圖形的算法時，就完成了。只是讓我們告訴你解決方案，你不會學到很多東西。