1

The simplest way to explain this is with an example.

You're given then number 19 and you have a set of numbers to choose from: 1, 2, 3, 4, 6

When choosing values from the list (which can be duplicates), the smallest number of values that adds up to 19 is 4:

6, 6, 6, 1

6, 6, 4, 3

Now the list of numbers I want to select is 6, 6, 4, 3 because when plotted on a graph, it draws a smoother gradient going from larger numbers to smaller numbers. 6, 6, 6, 1 is a sudden drop as it goes from the final 6 to the 1.

I may be wrong (and please correct me if so) but I think a better way of expressing that desire is to choose the list where the product of each of the numbers is the largest value.

6 * 6 * 6 * 1 = 216

6 * 6 * 4 * 3 = 432 (choose this list)

Another example is choosing 4, 3 instead of 6, 1 for a value of 7.

How could this be calculated using an algorithm (ideally non-brute-force!) for use with any total value and an arbitrary set of numbers to choose from?

3

This is the subset sum problem. The subset sum problem is NP-complete. In general the solution requires an exhaustive search, so the run time complexity is O(2^N) where N is the number of values in the set. Alternatively, if the desired sum S is small, dynamic programming can be used with a run time complexity of O(NS).

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.