3

如果我们有n个列表，我们需要从每个列表中选择一个数字，选择的数字不能再次选择，如何进行选择以获得n个选择的数字的最大和？例如

list1:  4 5 7.
list2:  3 5 7.
list3:  1 5

如果我们从list1中选择7，我们可以在列表2中选择的最大数字是5（因为相同的数字不能选择两次），如果我们从list2中选择5，我们只能从list3中选择1，所以总和是7+5+1=13

这不是最好的选择。但是，如果我们从 list1 中选择 4，从 list2 中选择 7，从 list3 中选择 5，则总和为4+7+5=16

是否有一种算法可以找到最佳选择方式以获得最大的总和？解决方案应该是完美的。

4

2 回答 2

4

没有直接的算法，但是，可以通过修改匈牙利算法在多项式时间内解决该问题。维基

给定一个非负 n×n 矩阵，其中第 i 行第 j 列中的元素表示将第 j 个工作分配给第 i 个工人的成本。我们必须找到成本最低的工作分配给工人。如果目标是找到产生最大成本的分配，则可以通过将每个成本替换为减去成本的最大成本来更改问题以适应设置。

构造维度为 (K*K) 的矩阵，其中 K=max(n,列表中元素的最大数量)。

例如：

List 1=1 2 3 4
List 2=5
List 3=9 10

The K*K matrix is:
1 2  3 4
5 0  0 0
9 10 0 0
0 0  0 0

将以下算法http://en.wikipedia.org/wiki/Hungarian_algorithm#Setting应用于上述矩阵。

于 2013-03-22T06:19:56.323 回答
0

由于我们已经对列表进行了排序并且列表的所有成员都是正数，因此列表中的最大数量应该在结果列表中。您还应该假设列表中的数字不会重复。否则没有意义。

List1 : 2 2 2 
List2 : 2 2

我们不需要迭代列表中的所有数字。在最坏的情况下，我们会遇到以前见过的 n-1 个数字。喜欢：

list1: 5 6 7
list2: 5 6 7
list3: 5 6 7

所以，我会这样做；

for list in lists:
   max = list[len(list)] 
   possible_result.append(max)
   for j = len(list) to j = len(list)-n in other lists:
      max = list[j]
      if not max exist in possible_result:
          append to possible_result
Find largest possible_result

第一次迭代将运行 n 次第二次，在最坏的情况下，n-1 次。

于 2013-09-22T16:27:08.983 回答