title: PHP - Packing widgets into the fewest number of boxes, plus minimum order quantity
body: <p>The problem is this:</p>
  
  <p>A company supplies widgets in a set of pack sizes:</p>
  
  <ul>
  <li>250</li>
  <li>500</li>
  <li>1000</li>
  <li>2000</li>
  <li>5000</li>
  </ul>
  
  <p>Customers can order any number of widgets, but the following rules apply:</p>
  
  <ul>
  <li>Only whole packs can be sent and …</li>
  <li>No more widgets than necessary should be sent and …</li>
  <li>The fewest packs possible should be sent</li>
  </ul>
  
  <p>Some examples showing the number of widgets ordered and the required pack quantities and sizes to correctly fulfill the order:</p>
  
  <ul>
  <li>1 (1 x 250)</li>
  <li>251 (1 x 500)</li>
  <li>501 (1 x 500 and 1 x 250)</li>
  <li>12001 (2 x 5000 and 1 x 2000 and 1 x 250)</li>
  </ul>
  
  <p>I’ve looked at some algorithms (greedy coin change, LAFF, etc.) as these seem to provide similar solutions. However, I'm ideally looking for a scalable, object oriented approach to solving this problem.</p>
  
  <p>Here's what I've come up with so far:</p>
  
  <pre><code>&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);
  </code></pre>