CODEWITHSUNDEEP
c#packingbinnp
user444651
user444651

Reputation: 39

Algorithm to determine best combinations - Bin Packing

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.

Upvotes: 3

Views: 3132

Answers (1)

Mark Byers
Mark Byers

Reputation: 838226

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:

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

Upvotes: 5

Related Questions