Search code examples
pythonalgorithmcombinationspython-itertools

Find the Highest Sum in a Combination of Numbers

Lets say I have this:

1A=6 2A=4.5  3A=6

1B=7 2B=6    3B=7.5

1C=6 2C=6.75 3C=9

I want to find the combination of numbers that yields the highest sum. None of the numbers before the letters can be used more than once and none of the letters after the numbers can be used more than once. eg. 1A+2B+3C, 1C+2B+3A are valid. 1A+1B+2B,3A+2B+3B,1A+2A+3A are invalid.

In this case the highest sum is 1A+2B+3C=21. How would I find this result and combination using python?

Thanks in advance

Solution

  • Actually, python has libraries that will do this for you. See here: Munkres