Hello /r/algorithms, I've made a new account just to make this post as I've had a problem that's been troubling me for a while. I've been working on a really interesting side-project that I've done the majority of the work for, but have gotten stuck with one key step.

The details don't matter, but I've managed to reduce it to this problem (which as an aside, can make for an interesting game), you are given a matrix / 2d array (I shall just say matrix from now on) and your goal is to select numbers from the matrix subject to certain conditions, such that their sum is maximal, the conditions are that:

- You can only select 1 entry from each row of the matrix

- For each column there is a given number of entries you can select (ie. column 1 may be able to pick 3, column 2 may be 21)

You can view an example 6x5 matrix with the number of column selections above, and the solution entries circled here.

This is an artificially constructed example of relatively small size that was relatively easy to solve by hand, but in what I'm working with I'm working with matrices with hundreds of rows and over a dozen columns, where entries can be very similar and it's not so easy to find standout figures.

If it makes a difference all of what I am working with will always fit within the subset of problems whereby the sum of the number of selections from all columns will be equal to the number of rows of the matrix.

Obviously an exhaustive solution is possible, but is extremely computationally intensive. I have considered whether I could use constraints programming, but I am using python so doing so is extremely difficult, and for what I am using it for I would prefer to find an algorithm. So I was wondering if anyone has encountered a similar problem or can come up with an algorithm which can help me in this situation?

I apologise as I'm just a maths / physics student and only well versed in python, so would prefer ideas for this language, but a general layout for an algorithm works just fine. I realise this problem likely just scales with the combinatorics no matter what, but I figured I'd ask here just in case anything can be identified for even polynomial time?

Thanks.