This question is somewhat similar to: Algorithm wanted: Enumerate all subsets of a set in order of increasing sums but has a significant difference in that instead of enumerating all subsets of a set, we need one value from each of a few pre-defined sets.
Suppose you have two or more columns (i.e. sets) of two or more numbers. The columns are sorted from the smallest to largest number. You must chose one number from each column. You want the numbers, when added together, to give you the lowest possible sum. The first answer is obvious - take the first number from each column. Now, what would be the exact algorithm that would find 'a number from each column' that would result in the next-lowest possible sum? And the next lowest, and the next, etc. Using brute-force (finding all possible combinations followed by a sort) is not permitted. You may re-arrange the columns if it's helpful. The procedure must be progressive and generic such that it could work on a much larger input. Here is an example:
0 0 0
9 1 16
17 22
sets:
1: 0+0+0 = 0
2: 0+1+0 = 1
3: 9+0+0 = 9
4: 9+1+0 = 10
etc...
The solution must show how to get the next set.
I've been trying to figure this out for two days now, any help would be highly appreciated. Thanks!