找到最佳組合的算法

-2

因此，我有12個列表，每個列表包含28個值的項目。找到最佳組合的算法

我想通過切換其他11個列表的項目來最大化第一個列表的值。

我也可以交易不同數量的物品。例如，我可以交易清單1中的6個項目和清單2中的3個項目。或者，我可以交易清單1中的19個項目和清單2中的22個項目。大型清單中還有其他項目不屬於清單的一部分，所以如果一個列表收到28個以上的項目，最低值很容易被丟棄，而如果一個列表少於28個項目，那麼可以很容易地添加新的項目。

但是，一個限制是我一次只能交易一個清單。例如，我不能從交易清單1交易3個項目到交易清單2，交易清單2交易3個項目到交易清單3，交易清單3交易3個項目到清單1.當我從清單1交易時，我只能一次交易一個單一的其他名單。

我可以明顯地蠻力這件事，但我覺得這將永遠。我對組合並不是很滿意，所以我不確定如果我想暴力，會有多少種不同的組合。

所以我的問題是，被暴力破解一個可行的解決方案在這裏，如果沒有，什麼是算法，可以幫助我的例子嗎？

謝謝，Krzys。

編輯：

例子：

List 1 
[Apple - 12] 
[Banana - 5] 
[Orange - 8] 

List 2 
[Steak - 15] 
[Chicken - 2] 
[Fish - 7] 

List 3 
[Zebra - 20] 
[Horse - 6] 
[Elephant - 10]

所以我會先從清單1.這是什麼程序會做：

if (List1.Apple - List2.Steak < BestTradeAvailable) Then BestTradeAvailable = List1.Apple - List2.Steak 
if (list1.Apple - List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = list1.Apple - List2.Chicken 
if (list1.Apple - list2.Fish < BestTradeAvailable) Then BestTradeAvailable = list1.Apple - list2.Fish 
if (list1.Banana - List2.Steak < BestTradeAvailable) Then BestTradeAvailable = list1.Banana - List2.Steak 
if (list1.Banana - List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = list1.Banana - List2.Chicken 
if (list1.Banana - List2.Fish < BestTradeAvailable) Then BestTradeAvailable = list1.Banana - List2.Fish

等我也想這樣做

if (list1.Apple + list1.Banana - List2.Steak + List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = list1.Apple + list1.Banana - List2.Steak + List2.Chicken

：一次這麼多個項目

但正如我之前說的，你可以從交易清單1一個項目，名單2 2項：

if (list1.Apple - List2.Steak + List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = List1.Apple - List2.Steak + List2.Chicken

所以基本上，我只是想嘗試找到可用的最佳交易。

在這個例子中，最好的交易是交易蘋果+橘子到項目list3斑馬和大象，因爲這個行業增長列表1的由最高金額總價值。

來源

2011-10-07 Krzys Czelusniak

這個問題是不可能理解的。給我們一個小例子，比如說四個列表，每個列表包含四個項目，展示您試圖最大化的數量。 –

@EricLippert我會舉一個例子。 –

那麼在你的例子中，什麼是最好的交易？你希望程序在這種情況下找到什麼結果？爲什麼？ –

基本上，你需要對列表進行排序，並將排名前28？

優先隊列將工作。

來源

2011-10-07 21:39:03

蠻力溶液將採取只爲O（n^2 *（M-1））的時間複雜度，其中n是在列表中，且m的項數是列表的數目。如果你想尋找所有的組合，它將是O（n^2 *（n-1）*（m-1））的時間複雜度，只有232848個組合，你必須嘗試。或者所有的組合都是n！如果訂單也很重要。

來源

2011-10-07 22:12:52 Bytemain

你確定嗎？從我自己總結的結果來看，使用nCr，如果我從總共28個球員中挑選了10名球員，我正在考慮與其他球隊進行交易，那麼28名球員中有10名球員的組合數量爲28C10，其中是13123110 ... –

你說你想最大化折衷，所以你不需要添加項目的順序組合。當訂單很重要時，28^10也是如此。 – Bytemain

掛上，我以爲nCr純粹是爲了組合，而nPr是物品的順序？如果沒有，並且你的回答是正確的，那麼我肯定會結束暴力強制這個。 –

找到最佳組合的算法

回答

相關問題