Get optimize list of a list of values

Question

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.

Can you generalize your problem? With your input, even a brute force approach will be very fast. — Mu Qiao
– Mu Qiao, Commented Sep 3, 2011 at 2:23
Take a look at: Algorithm to find which numbers from a list of size n sum to another number — Devendra D. Chavan
– Devendra D. Chavan, Commented Sep 3, 2011 at 4:58

svick · Accepted Answer · 2011-09-03 13:52:36Z

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.

answered Sep 3, 2011 at 13:52

svick

247k54 gold badges407 silver badges536 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Get optimize list of a list of values

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related