Problem Statment wrote: |
---|

Given an NxN grid of integers, you are allowed to choose only on integer per row and column. Choose N integers according to the above rules, such that their product is the greatest possible. |

I know that there are N! ways of choosing the correct result, but this is inefficient even for small N. Does anyone know an efficient solution?

Look up the Hungarian algorithm. It's along the same lines. This is really an "assignment problem." There are others, but I can't remember. I think you should be able to get this to O(n^3) or O(n^2). The product is really trivial, your just looking for the N largest numbers not in the same row or column.

Last edited on

Topic archived. No new replies allowed.