Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a set of $n$ numbers, representing quantities of a given product in pallets
I have to fulfill an order of $k$ pieces

order : 165
pallets: [ 150, 20, 5, 50, 80, 120, 15, 10 ]

I want to find the partition which:
1. sums up to at least 165 but contains as little pallets as possible.
2. has minimum cardinality

1 : [150, 20]      sum: 170, cardinality 2
2 : [150, 10, 5]   sum: 165, cardinality 3
3 : [150, 15]      sum: 165, cardinality 2

3 is chosen.

Can you give a name to this mathematical problem?
Is there a fast algorithm, even with approximation?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Instead of choosing the set, choose the complementary set; you then have a maximum sum on the complementary set, and you want to maximize the number of pallets; I believe this is then a knapsack problem.

http://en.wikipedia.org/wiki/Knapsack_problem

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.