Algorithm to determine best combinations - Bin Packing

Question

Given a set of items, each with a value, determine the number of each item to include in a collection so that the total value is less than or equal to given limit and the total value is as large as possible.

Example:

Product A = 4
Product B = 3
Product C = 2
Product D = 5

If Total Capacity = 10.5 , then the combination of B,C,D will be selected.
If Total Capacity = 12.5 , then the combination of A,B,D will be selected.
If Total Capacity = 17 , then the combination of A,B,C,D will be selected.

I am looking for an algorithm (like knapsack or bin packing) to determine the combination. Any help appreciated.

Answer 1

You say that this is "like knapsack". As far as I can see it is a special case of bounded knapsack problem called the 0-1 knapsack problem.

It is NP-complete.

There are lots of ways you could attempt to solve it. See this related question for one approach:

• Writing Simulated Annealing algorithm for 0-1 knapsack in C#

If you only have four items then just testing all possibilities should be fast enough for most purposes.