Ggthjy

The problem is this:

A company supplies widgets in a set of pack sizes:

• 250


• 500


• 1000


• 2000


• 5000

Customers can order any number of widgets, but the following rules apply:

• Only whole packs can be sent and …


• No more widgets than necessary should be sent and …


• The fewest packs possible should be sent

Some examples showing the number of widgets ordered and the required pack quantities and sizes to correctly fulfill the order:

• 1 (1 x 250)


• 251 (1 x 500)


• 501 (1 x 500 and 1 x 250)


• 12001 (2 x 5000 and 1 x 2000 and 1 x 250)

I’ve looked at some algorithms (greedy coin change, LAFF, etc.) as these seem to provide similar solutions, but can’t seem to see how to adapt them to the above.

For example:

<?php



function countWidgets($amount) 

{ 

    $packs = array(5000, 2000, 1000, 500, 

                  250); 

    $packCounter = array(0, 0, 0, 0, 0); 

    $packsCount = count($packs);



    // loop packs

    for ($i = 0; $i < $packsCount; $i++)  

    { 

        if ($amount >= $packs[$i]) 

        { 

            $packCounter[$i] = intval($amount /  

                                      $packs[$i]); 

            $amount = $amount -  

                      $packCounter[$i] *  

                      $packs[$i]; 

        } 

    }



    // if remainder

    if ($amount > 0) {

        // and if smallest pack size populated

        if ($packCounter[4] == 1) {

            // clear smallest pack size

            $packCounter[4] = 0;

            // increment next biggest pack size

            $packCounter[3] += 1;

        } else {

            // increment smallest pack size

            $packCounter[4] +=1;

        }

    }





    // Print packs 

    echo ("Pack ->"."n"); 

    for ($i = 0; $i < $packsCount; $i++)  

    { 

        if ($packCounter[$i] != 0)  

        { 

            echo ($packs[$i] . " : " . 

                  $packCounter[$i] . "n"); 

        } 

    } 

} 



$amount = 251; 

countWidgets($amount);

OK, I agree that this is a bit harder than I assumed yesterday. You basically have two opposing demands:

1. No more widgets than necessary should be sent.


2. The fewest packs possible should be sent.

You cannot fulfill both. So if I tried to send 1200 widgets, rule 2 says I should send a pack of 2000, however, rule 1 says I should send 2 packs: one of 1000 and one of 250. Which rule should prevail?

I chose that rule 1 should prevail in the solution below. The reason is that no customer wants more widgets than absolutely necessary.

$packSizes = [ 250,

               500,

              1000,

              2000,

              5000];



function optimizePacks($packSizes,$number)

{

    rsort($packSizes);

    $requiredPacks = array_fill_keys($packSizes,0);

    foreach ($packSizes as $size) {

        $packs = floor($number/$size);

        if ($packs > 0) {

            $requiredPacks[$size] = $packs;

            $number -= $packs*$size;

        }

    }

    if ($number > 0) $requiredPacks[min($packSizes)]++;

    return $requiredPacks;

}



$packs = optimizePacks($packSizes,6666);



print_r($packs);

This will work for any array of pack sizes and any number of widgets. The output of this code is:

Array (
[5000] => 1
[2000] => 0
[1000] => 1
[500] => 1
[250] => 1 )

Which is one pack more than rule 2 would demand (one of 5000 and two of 1000). It would, of course, be possible to let rule 2 prevail, but I cannot fulfill both rules.

Here is one using a while loop and simple subtaction:

$packSizes = [250,500,1000,2000,5000];

$number = 3000;              



function optimizePacks($packSizes,$number)

{

    //insure packs are in decending order

    rsort($packSizes);

    //create a default array

    $results = array_fill_keys($packSizes, 0);



    while($number > 0){

        echo "---------- $number ----------n";



        foreach($packSizes as $size){

            if($size <= $number) break;

        }

        ++$results[$size];

        $number -= $size;

    }

    return $results;

}



$tests = [

    1,      // (1 x 250)

    251,    // (1 x 500)

    501,    // (1 x 500 and 1 x 250)

    12001   // (2 x 5000 and 1 x 2000 and 1 x 250)



];



foreach($tests as $test) print_r(optimizePacks($packSizes,$test));

Output

---------- 1 ----------

Array

(

    [5000] => 0

    [2000] => 0

    [1000] => 0

    [500] => 0

    [250] => 1

)

---------- 251 ----------

---------- 1 ----------

Array

(

    [5000] => 0

    [2000] => 0

    [1000] => 0

    [500] => 0

    [250] => 2 //deviates from your example output (see below)

)

---------- 501 ----------

---------- 1 ----------

Array

(

    [5000] => 0

    [2000] => 0

    [1000] => 0

    [500] => 1

    [250] => 1

)

---------- 12001 ----------

---------- 7001 ----------

---------- 2001 ----------

---------- 1 ----------

Array

(

    [5000] => 2

    [2000] => 1

    [1000] => 0

    [500] => 0

    [250] => 1

)

Sandbox

These 2 examples are at odds with each other

251,    // (1 x 500)

501,    // (1 x 500 and 1 x 250)

The first one you make one incomplete 500 part box

The second one you make a 500 (complete box) and an extra 250 with one part.

So the question is, why is the first one only 1 box as it should be 250 x 2 boxes. Conversely why is the second 2 boxes when it could be 1000 x 1 boxes.

So either you fit them in the smallest box that can contain them with the extra overflowing. Or you put them in complete boxes and put the remainder in the smallest box.

UPDATE

If you want the reverse I came up with this:



$packSizes = [250,500,1000,2000,5000];



function optimizePacks($packSizes,$number)

{

    //insure packs are in ascending order

    sort($packSizes);

    //create a default array

    $results = array_fill_keys($packSizes, 0);



    while($number > 0){

        echo "---------- $number ----------n";



        foreach($packSizes as $size){

            if($size >= $number) break;

        }



        ++$results[$size];

        $number -= $size;

    }

    return $results;

}



$tests = [

    1,      // (1 x 250)

    251,    // (1 x 500)

    501,    // (1 x 500 and 1 x 250)

    12001   // (2 x 5000 and 1 x 2000 and 1 x 250)



];



foreach($tests as $test) print_r(optimizePacks($packSizes,$test));

Output

---------- 1 ----------

Array

(

    [250] => 1

    [500] => 0

    [1000] => 0

    [2000] => 0

    [5000] => 0

)

---------- 251 ----------

Array

(

    [250] => 0

    [500] => 1

    [1000] => 0

    [2000] => 0

    [5000] => 0

)

---------- 501 ----------

Array

(

    [250] => 0

    [500] => 0

    [1000] => 1  //deviates from your example output

    [2000] => 0

    [5000] => 0

)

---------- 12001 ----------

---------- 7001 ----------

---------- 2001 ----------

Array

(

    [250] => 0

    [500] => 0

    [1000] => 0

    [2000] => 0

    [5000] => 3  //deviates from your example output

)

This also points out how the last example is at odds with this way. Which is to fit the most parts in the smallest size box. This may be a bigger box but it will not overflow. For example it wont pick 5000 for 1 part.

I used a pretty nice trick with the foreach in the above code, that let me simplify it greatly.

This only works if you sort it ASC, because if we don't find a box that can hold the full number, the last iteration leaves $size at the Max value in the array (its the last one after all). Which is exactly what we want because then we subtract that from $number and repeat the process.

However if we do find a box that can contain all the parts, we simply exit (break) the foreach loop. This will be the smallest box that can fit all the parts (naturally). And we also subtract this which will leave $number at <= 0 and break the while loop which completes the function and returns the results.

Sandbox

If you really want them (the sizes, compare the 2 results in my examples) in the other order, we can either send them in that order and build the default first, or sort one way build the default then reverse the array (which should be faster then sort).

function optimizePacks($packSizes,$number)

{

    //insure packs are in decending order

    rsort($packSizes);

    //create a default array (baking in the order)

    $results = array_fill_keys($packSizes, 0);

    //flip the order

    $packSizes = array_reverse($packSizes);





    while($number > 0){

Sandbox

Summery

Essentially you can't have both of these (or your mixed examples) without a whole lot of conditional statements that would violate using a dynamic array of sizes. You could do that with fixed sizes and special if conditions, for example. This is because your inconsistently applying your rules.

Hope it helps, I get some weird enjoyment out of figuring this stuff out... lol