通過交易最大化利潤

我一直在這個問題上停留了一段時間，試圖找出以下問題的重現關係。通過交易最大化利潤

問題描述：

假設在市場以下列商品選項是可能的：

1金屬〜2木材
1木至0.2玻璃
1玻璃至1.5金屬
1木材0.4火
1火3金屬

確定是否有可能通過交易賺取某個項目的利潤。

例如，在上面所描述的情況下，我們可以通過以下操作使上金屬利潤： - > 2木材 - > 0.8火災 -

1金屬> 2.4金屬

的部分，其中我被困住的是子問題應該如何分解。對於括號乘法問題，這個問題似乎很熟悉，我們試圖通過一系列乘法使最終結果最大化，但有更多的限制。

我不想完整的答案，但提示可以推動我走向正確的方向將非常感激！

謝謝！

來源

2016-03-13 tempNULL

提示：這看起來像一個可以很好地表示爲圖形的問題。這個圖表中的解決方案是什麼樣的？你能證明，如果有解決方案，那麼必須有一個*最小的*這樣的解決方案，它有一些特別簡單的結構？ –

我會將此作爲一個圖形問題來處理。每一項都是一個節點，每一個可能的交易都是一個邊緣那麼什麼決定了一個有利可圖的交易場景 –

@j_random_hacker謝謝，我會試試看，它似乎更簡單的一個圖形問題！ – tempNULL

提示：您可以通過「玩」權重並將其減少到已知加權最短路徑問題來解決此問題。

擾流：詳細說明

這可通過查找在圖上的負懷特週期很好地解決了，配重塊：

讓w'(u,v)是轉化的u一個單元的成本到v。定義：

w(u,v) = -log(w'(u,v))

的想法是一個路徑v1->v2->...->vk具有

COST = w(v1,v2) + w(v2,v3) + ... + w(vk-1,vk) = 
    = -log(w'(v1,v2)) + -log(w'(v2,v3)) + ... + -log(w'(vk-1,vk)) = 
    = -log (w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk))

成本現在，人們容易看到的w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk)值是完全相同的vk從一個單元所產生的量v1。

同樣，對於一些u本身任何週期：u->v1->v2->v3->...vk->v的w'(u,v1)*w'(v1,v2),...,w'(vk,u)值，你可以有多少單位產生這樣，該值是大於1，當且僅當-log(w'(u,v1)*w'(v1,v2),...,w'(vk,u) < 0

所以，這問題可以很容易地減少到一個已知的算法 - Bellman-Ford，它可以輕鬆檢測到負循環的存在。

來源

2016-03-13 17:38:44 amit

謝謝！這很有道理！ – tempNULL

通過交易最大化利潤

回答

相關問題