3

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.

Oded
  • 489,969
  • 99
  • 883
  • 1,009
user444651
  • 39
  • 2
  • 4
  • 2
    What's the context for this question? Is this an actual problem you need to solve? Is it homework? – Mark Byers Sep 10 '10 at 21:05
  • I am not a student. This is for finding the best combination of Fixed discounts for a product. The shopping cart should be automatically find the highest value of discounts from the given discounts(eligible discounts for a product). For example: If a product costs $30 and it is eligible for $5 off ,$10 off and $50 Off, the cart should select $5 and $10. I already put together algorithm using combination number theory. I am looking for some more tips or an algorithm for this scenario. any help appreciated. – user444651 Sep 11 '10 at 02:30

1 Answers1

5

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.

Community
  • 1
  • 1
Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452