算法：從每個列表中選擇一個數字，找到最大數額

如果我們有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

算法：從每個列表中選擇一個數字，找到最大數額

回答

相關問題