1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Do you have a reason to think there is a nice solution? If so, please tell us what this reason is; that will be helpful for choosing promising places to look for it. $\endgroup$ – Henning Makholm May 5 '16 at 19:59
  • $\begingroup$ @HenningMakholm the biggest reason I have to believe there can be a good solution is due to the post I mentioned which contains an excellent solution to a similar problem. $\endgroup$ – scybolt May 5 '16 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.