1
$\begingroup$

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 Answers 1

2

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