# Math Help - Combinatory optimization problem

1. ## Combinatory optimization problem

Dear experts,

for a practical use in a warehouse I'm searching for a way to define this problem in an algorithm:

We need to pick an article with a given amount $x$ where $x \in \mathbb N^+$.
The article is distributed in several boxes in the warehouse. Each box contains the article in different amounts. So we have a limited amount of boxes $n$ with each box containing a quantity $y_n$ where $y_n \in \mathbb N^+$. We want to find the combination of boxes where the sum of the quantity of all selected boxes gets as close as possible to $x$ (but doesn't exceed $x$).

$
\begin{array}{|c||c|c|c|c|c|c|c|}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
y_n & 15 & 17 & 8 & 20 & 19 & 20 & 18\\
\hline
\end{array}
$

if $x=53$ then the ideal combination would be $y_1+y_4+y_7$ (15+20+18=53).
if $x=30$ the best combination would be $y_3+y_4$ (8+20=28).

It looks a little bit like a 0-1 knapsack problem to me but without the maximimizing of a value. Performance would certainly have to be considered. Can you help me to find an algorithm (I guess this problem is NP-hard)?

Regards,
Gunter