PHP - Packing widgets into the fewest number of boxes, plus minimum order quantity 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:

&lt;?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 &lt; $packsCount; $i++)  
    { 
        if ($amount &gt;= $packs[$i]) 
        { 
            $packCounter[$i] = intval($amount /  
                                      $packs[$i]); 
            $amount = $amount -  
                      $packCounter[$i] *  
                      $packs[$i]; 
        } 
    }

    // if remainder
    if ($amount &gt; 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 -&gt;"."\n"); 
    for ($i = 0; $i &lt; $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: 


No more widgets than necessary should be sent. 
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 &gt; 0) {
            $requiredPacks[$size] = $packs;
            $number -= $packs*$size;
        }
    }
    if ($number &gt; 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.