Minimum k elements of an mxn matrix with the constraint that none of the elements can be in the same row / column
I have a dynamic programming question (maybe a greedy one).
Let A be an mxn matrix. Let k be an integer such that k & leq; min {t, n}.
Find k elements from A for which each of these k elements is in their unique column and row; and the sum of these k elements is minimized.
In other words, I want to select k elements from A so that their sum is minimal; but if i choose A 2,3then I cannot choose A 2.6 or 4,3...
The greedy approach seems to fetch the minimum element in A, remove its row and column, and repeat until A is exhausted. However, I cannot prove the greedy property in this case, or even if it has the greedy property.
I also couldn't figure out how to build a table for the DP solution.
If this problem has been raised earlier and has a specific name, can you share it?
source to share
The greedy will not cut off. You need a Hungarian algorithm engine. One might think about creating nk new rows and mk new columns, which makes new row-new column entries very unattractive and other new entries very attractive. Then find a cost-effective solution that matches rows with columns one-to-one and throws out pairs containing a new row or column.
In real practice, there will be a better implementation, but its description requires me to describe the HA details.
source to share
A greedy algorithm will not provide an optimal solution. Suppose A11 = 0, A12 = A21 = 1, everything else = 1000. The smallest sum is found by taking A12, A21 and any k-2 other values, 1000k in total - 1998. Choosing A11 = 0 first forces you to choose k -1 values 1000, for a total of 1000 thousand - 999.
source to share