Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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.

share|cite|improve this answer

Your Answer


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.