算法：从每个列表中选择一个数字，找到最大数额

如果我们有n个列表，我们需要从每个列表中选择一个数字，所选择的数字不能再被选择，如何进行选择以获得最大的总和n选定的号码？例如算法：从每个列表中选择一个数字，找到最大数额

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

如果我们选择7从list1的，最大的数，我们可以选择在列表2是5（因为同样数量不能被选择两次），如果我们从列表2选择图5，我们只能选择1从项目list3，所以总数是7+5+1=13

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

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

来源

2013-03-22 Yijie Li

也许Knuth的“跳舞链接”算法？ – comocomocomocomo 2013-03-22 04:48:43

这可能是一个难以解决问题的NP难题。你的解决方案必须是完美的还是只需要做得好？ – Wug 2013-03-22 04:53:48

我们可以假设每一行已经排序？ – jamylak 2013-03-22 05:12:56

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

我们给出一个非负的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-22 06:19:56

有没有比多项式时间更好的解决方案？ – 2013-03-22 17:55:57

我不认为比匈牙利有更好的算法存在这个问题。 – 2013-03-22 18:55:28

这似乎不是同一个问题。这具有约束，即相同的*列*不能被使用两次，而OP限制使用相同的*值*两次。 – RBarryYoung 2013-09-22 16:32:41

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

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-22 16:27:08 NiceCoder

算法：从每个列表中选择一个数字，找到最大数额

回答

相关问题