寻找最佳组合的算法

Question

因此，我有 12 个列表，每个列表包含 28 个具有值的项目。

我试图通过与其他 11 个列表交换项目来最大化第一个列表的价值。

我还可以交易不同数量的物品。例如，我可以交易列表 1 中的 6 个项目和列表 2 中的 3 个项目。或者，我可以交易列表 1 中的 19 个项目和列表 2 中的 22 个项目。大型池中还有不属于列表的其他项目，因此，如果列表接收的项目超过 28 个，则可以轻松删除最低值，如果列表的项目少于 28 个，则可以轻松添加新项目。

然而，一个限制是我一次只能使用一张列表进行交易。例如，我不能将列表1中的3个项目交易到列表2，将列表2中的3个项目交易到列表3，以及将列表3中的3个项目交易到列表1。当我从列表1进行交易时，我只能一次与一个其他列表进行交易。

显然我可以用蛮力来实现这一点，但我觉得这需要很长时间。我不太擅长组合，所以我不确定如果我想要暴力破解会有多少种不同的组合。

所以我的问题是，暴力破解在这里是否是一个可行的解决方案，如果不是，有什么算法的例子可以帮助我？

谢谢，克日斯。

编辑：

示例：

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

所以基本上，我只想尝试找到可用的最佳交易。

在此示例中，最佳交易是将 Apple + Orange 交易到 List3 换取 Zebra 和 Elephant，因为此交易使 List1 的总价值增加了​​最高金额。

Answer 1

本质上您需要对列表进行排序并取出前 28 个？

优先队列会起作用。

Answer 2

暴力解决方案仅需要 O(n^2 * (m-1)) 时间复杂度，其中 n 是列表中的项目数，m 是列表数。如果你想查找所有组合，时间复杂度为 O(n^2 * (n-1) * (m-1))，你只需尝试 232848 个组合。或者所有组合都是n！如果顺序也很重要。