Results 1 to 1 of 1

Math Help - Combinatory optimization problem

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    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).

    Example for 7 boxes of this article:
    <br />
\begin{array}{|c||c|c|c|c|c|c|c|}<br />
   \hline<br />
 n & 1 & 2 & 3 & 4 & 5 & 6 & 7\\<br />
\hline<br />
  y_n & 15 & 17 & 8 & 20 & 19 & 20 & 18\\<br />
   \hline<br />
\end{array}<br />

    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
    Last edited by Skye; April 2nd 2010 at 10:49 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Little optimization problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: May 14th 2010, 10:10 AM
  2. Optimization Problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 8th 2010, 09:30 AM
  3. combinatory question
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 14th 2009, 08:13 AM
  4. Combinatory Counting help
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: February 14th 2009, 09:07 AM
  5. Combinatory problem
    Posted in the Statistics Forum
    Replies: 3
    Last Post: November 28th 2008, 05:36 PM

Search Tags


/mathhelpforum @mathhelpforum