This is a part of algorithmic problem I’m fighting with for the 3rd day in the row. So we are given an array 3xn (n rows, 3 columns). We need to find the least sum such:
- we only pick one element from each row,
- each row must be represented, so there has to be exactly one number from each row in such sum,
- each column must be represent, so there has to be at least one number located 1st column, at least one located in the 2nd column, and at least one in the 3rd column.
Let’s take that array to illustrate the problem:
6 2 4
8 7 5
6 2 4
9 6 5
The least sum in that case is 8 (1st column, 2nd row) + 2 (2nd column, 1st row) + 5 (3rd column,4th row) + 2 (2nd column,3rd row) = 17
I tried solving that in such greedy way that I created three copies of that array, sorted each of them by the respective column and then tried in 3! ways to make the least sum of the three numbers, and add the minimums for the rest, but then solution for the above case would be:
6 (1st column, 3rd row) + 2 (2nd column, 1st row) + 5 (3rd column, 4th row) + remaining 5 (3rd column, 2nd row) = 18 So that way of greedy approach proved to be unsuccessful. Would anyone suggest what should I change in my approach to make it the workin’ one?