0

Sorry couldn't think of a better title. So here is an example of my problem. I have a list of items that have values such as 120, 100, 70, 65, 30 20. Now I want combination of 3 of these that will be close to 165.

I was looking into solutions using the napsack idea however I don't know how to make some of the solutions for that work when we have two limiting factors being number of items allowed and the max value.

Any direction or help would be great.

We could use the example I gave... List we have 120,100,70,65,30,20 I'm looking for a combination of 3 numbers that is under 165. I'm hoping that the system I use will be scalable to change both the 165, and number allowed in the combination.

MrB
  • 1,544
  • 3
  • 18
  • 30
  • Can you generalize your problem? With your input, even a brute force approach will be very fast. – Mu Qiao Sep 03 '11 at 02:23
  • 1
    Take a look at: [Algorithm to find which numbers from a list of size n sum to another number](http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number) – Devendra D. Chavan Sep 03 '11 at 04:58

1 Answers1

2

The pseudo-polynomial solution to subset sum problem can be used to solve your problem too.

Execute the algorithm described there and then look for the highest number s smaller than 165 for which Q(n, s) is true.

svick
  • 236,525
  • 50
  • 385
  • 514