找到最佳组合的算法

-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是物品的顺序？如果没有，并且你的回答是正确的，那么我肯定会结束暴力强制这个。 –

找到最佳组合的算法

回答

相关问题