# Minimum sum partition with a lower bound

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?

-

## 1 Answer

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

-