Shipping Calculation Class Woes

absolute0net

The Scenario: I'm writing a method that will calculate the total number of items. Then, if the item count is over 25, it needs to go into a second package, and so and so on.

What I want:
1) Calculate the number of total items
2) Loop through the total number of items and add the weight of each item until it reaches 25, then start a new package.

So if I have an order with 53 items:
20, 1lb widgets
25, 2lb widgets
8, 3lb widgets

Ideally, I would have the following result.
3 Total packages.
Pkg #1: Would have 25 items with a weight of 30 lbs. (201lb + the 52lb to fill up the first box).

Pkg #2: Would also have 25 items with a weight of 55 lbs. (202lb + the 53lb to fill up the second box).

Pkg #3: Would have the remaining 3 items with a weight of 15lbs.

My problem is that for some reason, I cannot wrap my head around this concept.

Any tips, tutorials or advice is welcomed.

brendan2b

This should help a little bit.



function calculatePackages($items, $weights)
{
        // the $items and $weight arguments in my example are single dimension   

        // arrays perfectly aligned.

    // we create a two dimensional array to hold the items and total weight for
    // that package

    $totalItems = sizeof($items);

    // item counter
    $i = 0;
    // package counter
    $k = 0;
    // items in each package counter
    $j = 0;

    while($i < $totalItems)
    {
         // this will check to see if we have fit a full package, if we have we 
         // increment $k and reset $j
         if(($i % 25) == 0)
         {
                 $k++;
                 $j = 0;
         }
        else
        {
               $package[$k][$j] = $items[$i];
               $package[$k]["weight"]  .= $weights[$i];
               $j++;
         }

         $i++;
     }


     return $package;




}

I threw that together pretty quickly but it should really give you an idea of how you should go ahead and figure out your issue.

absolute0net

Thanks for the code snip... much appreciated.

laserlight

hmm... a word of warning though: I am not very well versed on the subject, but if you intend to minimise the number of packages, then I believe that this is an instance of the bin packing problem, which is NP-hard. brendan2b's suggestion sounds good, but it is likely to be sub-optimal (not his fault though: if this is really the bin packing problem, then the best computer scientists in the world do not know the optimal algorithm).

brendan2b

Oh didn't you read my profile? I am actually one of those great computer scientists you speak of.

HAH just kidding... : ]

But yes, laserlight is correct. My approach will only be useful to you if you are trying to just add all the items you have into 25 item packages WITHOUT caring about total weight or number of packages.

If this is truly the bin packing algorithm then well you really can't ask for a great solution because NP-hard problems most of the time have "good enough" algorithms, in which you just simply cannot search and find the most optimal one.

Good luck with your packaging!