1

I'm a layperson when it comes to maths so I don't know exactly what terms I should use to search for, or even describe the problem, so apologies if this is a duplicate already answered. I come from a programming background. This example is a simplification of the actual problem. Say I have a table of values for combinations 1A, 1B, 1C, 1D, 2A etc:

A B C D
1 12 10 09 08
2 10 03 02 01
3 03 09 04 03
4 01 02 07 05
5 01 02 02 02
6 01 01 01 01

Using only 4 out of the 6 rows say, I need an algorithm that will efficiently find the largest total of column values for the 4 rows without duplicating a column. So for this table the highest value I can find is 34 using 1D, 2A, 3B and 4C. Of course I could write a routine that just looked at all possible combinations. For this case that would be fine, but with larger numbers of elements it would take too long. Is there a maths short cut out there that can help me?

John Fowler
  • 13

1 Answers1

0

In this scenario, as you are only choosing a single number from each column, first you can look for the largest number in each column. If they are all in different rows, then the problem is solved and you are done.

However, if more than one of the values is in a given row (for example, all of the columns in your table have their highest value in row 1), look for the second-highest in each column (A=10; B=9; C=7; D=5). Then, find the difference between your first- and second-highest values (A=2; B=1; C=2; D=3). This shows how much the total will go down if you change the value in a given column. Finally, keep the value that would harm the total the most (in this case, D), and move all the others to the second-highest value. Repeat this process until all the values are in different rows.

In this scenario, the highest value possible for the sum of 4 numbers, all in different columns and rows is 34 (10+9+7+8).

PiGuy314
  • 637