algorithm: select a number from each list, find the largest sum

Question

if we have n lists, we need to select a number from each list, the selected number cannot be selected again, how to make selection to get the largest sum of n selected numbers? e.g.

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

if we select 7 from list1, the largest number we can select in list 2 is 5(because same number cannot be selected twice), if we select 5 from list2, we can only select 1 from list3, so the sum is 7+5+1=13

it is NOT the best selection. however, if we select 4 from list1, 7 from list2, 5 from list3, the sum is 4+7+5=16

Is there a algorithm to find the best way to make selection in order to get the largest sum? The solution should be perfect.

This might be an NP-hard problem to always solve optimally. does your solution have to be perfect or does it just have to be good? — Wug
– Wug, Commented Mar 22, 2013 at 4:53

Ritesh Kumar Gupta · Accepted Answer · 2013-03-22 06:33:15Z

4

There is no direct algorithm for it, however, the problem can be solved in a polynomial time by modifying Hungarian Algorithm. WIKI

We are given a nonnegative n×n matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers that has minimum cost. If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.

Construct the matrix of dimension (K*K), where K=max(n,maximum number of elements in a list).

For example:

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

Apply the following Algorithm http://en.wikipedia.org/wiki/Hungarian_algorithm#Setting to the above matrix.

edited Mar 22, 2013 at 6:33

answered Mar 22, 2013 at 6:19

Ritesh Kumar Gupta

5,2018 gold badges51 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Yijie Li Over a year ago

Is there a better solution than polynomial time?

Ritesh Kumar Gupta Over a year ago

I don't think a better algorithm than Hungarian exists for this problem.

RBarryYoung Over a year ago

This does not appear to be the same problem. This has the constraint that the same column cannot be used twice, whereas the OP restricts using the same value twice.

NiceCoder · Accepted Answer · 2013-09-22 16:27:08Z

Since we have sorted lists and all members of the list is positive, the largest number of one of the list should be in the result list. You should also assume that the numbers in a list does not repeat themselves. Doesn't make sense otherwise.

List1 : 2 2 2 
List2 : 2 2

We don't need to iterate all numbers in a list. In worst case we would came across n-1 numbers we have seen before. Like:

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

So, I would do this;

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

First iteration would run n times second one, in worst case, n-1 times.

Collectives™ on Stack Overflow

algorithm: select a number from each list, find the largest sum

2 Answers 2

3 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Related