title: algorithm to find the number of boxes needed for different lengths of cable
body: <p>Given that someone can purchase cable in boxes of 10K, 5K, 2K, 1K feet.</p>
  
  <p>Suppose they have 100 cable drops of different lengths.</p>
  
  <p>I want to determine the best combination boxes they would need to purchase to 
  minimize the amount of wasted cable to create their drops.</p>
  
  <p>What is the best way to go about doing this? I'm not good with algorithms :(</p>
  
  <p>Simplified example of what I'm trying to accomplish:</p>
  
  <p>You have the following cable lengths:</p>
  
  <p>1, 1, 2, 3, 4, 5, 6, 7, 5, 4, 3, 2</p>
  
  <p>You have the following box sizes:</p>
  
  <p>5, 10, 20</p>
  
  <p>Given the cable lengths, to minimize waste you would need to purchase:</p>
  
  <p>2 x 20 boxes </p>
  
  <p>1 x 5 box</p>
  
  <hr>
  
  <p>20 = 7, 3, 6, 4</p>
  
  <p>20 = 5, 5, 2, 3, 4, 1</p>
  
  <p>5 = 1, 2</p>
  
  <p>=======================================</p>
  
  <p>Just for anyone else that needs something like this in the future. Here is the completed code to the original problem. It's a Frankenstein from cutting and pasting and gluing together different solution that I found, though it works on my box . I want to thank @bryan60 again for the initial part of this solution, you did an outstanding job and really help get this solution off the ground. </p>
  
  <pre><code>    "use strict";
  
      //Knapsack algorithm
      //==================
      // wikipedia: [Knapsack (0/1)](http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem)
      // Given a set `[{weight:Number, benefit:Number}]` and a capacity,
      // find the maximum value possible while keeping the weight below
      // or equal to the capacity
      // **params**:  
      //    `capacity`  : Number,  
      //    `items`     : [{w:Number, b:Number}]  
      // **returns**:  
      //    An object containing `maxValue` and `set`
      function knapsack(items, capacity) {
          var idxItem = 0,
              idxWeight = 0,
              oldMax = 0,
              newMax = 0,
              numItems = items.length,
              weightMatrix = new Array(numItems + 1),
              keepMatrix = new Array(numItems + 1),
              solutionSet = [];
  
          // Setup matrices
          for (idxItem = 0; idxItem &lt; numItems + 1; idxItem++) {
              weightMatrix[idxItem] = new Array(capacity + 1);
              keepMatrix[idxItem] = new Array(capacity + 1);
          }
  
          // Build weightMatrix from [0][0] -&gt; [numItems-1][capacity-1]
          for (idxItem = 0; idxItem &lt;= numItems; idxItem++) {
              for (idxWeight = 0; idxWeight &lt;= capacity; idxWeight++) {
  
                  // Fill top row and left column with zeros
                  if (idxItem === 0 || idxWeight === 0) {
                      weightMatrix[idxItem][idxWeight] = 0;
                  }
  
                  // If item will fit, decide if there's greater value in keeping it,
                  // or leaving it
                  else if (items[idxItem - 1].w &lt;= idxWeight) {
                      newMax = items[idxItem - 1].b + weightMatrix[idxItem - 1][idxWeight - items[idxItem - 1].w];
                      oldMax = weightMatrix[idxItem - 1][idxWeight];
  
                      // Update the matrices
                      if (newMax &gt; oldMax) {
                          weightMatrix[idxItem][idxWeight] = newMax;
                          keepMatrix[idxItem][idxWeight] = 1;
                      }
                      else {
                          weightMatrix[idxItem][idxWeight] = oldMax;
                          keepMatrix[idxItem][idxWeight] = 0;
                      }
                  }
  
                  // Else, item can't fit; value and weight are the same as before
                  else {
                      weightMatrix[idxItem][idxWeight] = weightMatrix[idxItem - 1][idxWeight];
                  }
              }
          }
  
          // Traverse through keepMatrix ([numItems][capacity] -&gt; [1][?])
          // to create solutionSet
          idxWeight = capacity;
          idxItem = numItems;
          for (idxItem; idxItem &gt; 0; idxItem--) {
              if (keepMatrix[idxItem][idxWeight] === 1) {
                  solutionSet.push(items[idxItem - 1]);
                  idxWeight = idxWeight - items[idxItem - 1].w;
              }
          }
          return { "maxValue": weightMatrix[numItems][capacity], "set": solutionSet };
      }
  
      function removeItem(items, value) {
          //console.log(items, "items:before");
          //console.log(value, "value");
          let found = false;
          items.forEach(function (e, i, arr) {
              //console.log(e, "e");
              if (e["w"] == value["w"] &amp;&amp; !found) {
                  items.splice(i, 1);
                  found = true;
              }
          });
          //console.log(items, "items:after");
          return items;
      }
  
      function getTotal(items){
          var s = items.reduce((a,b) =&gt; a + parseFloat(b["w"]), 0);
          return s;
      }
  
      /*
        lengths: array - array of numbers represents the different lengths of cable
        boxes: array - array of numbers represents the different sizes of boxes for cable length
      */
      function main(lengths, boxes) {
          let ret = {
              boxes: {},
              cart: [],
              total: 0
          }
  
          //ret.total = lengths.reduce((a, b ) =&gt; a + b, 0 );
          // sort boxes ascending
          boxes = boxes.sort((b1, b2) =&gt; b2 + b1);
          console.log(boxes);
          let items = [];
          lengths.forEach(function (i) {
              items.push({ "w": i, "b": i })
          });
          let grandTotal = getTotal(items);
  
          ret.total = grandTotal;
  
          console.log(ret);
          let prevLength = items.length
          while(items.length &gt; 0){
              // get total amount of the items
              let total = getTotal(items)
              // see which box is the smallest we can fit
              let boxSize = 0
              boxes.forEach(function(v,i,a){
                  if(v &lt;= total){
                      boxSize = v;
                  }
              });
              // break if we can't find a box
              //console.log(boxSize);
              if(boxSize == 0){
                  break;
              }
              // invoke knapsack
              let result = knapsack(items, boxSize);
              // if the maxValue == 0 then we actually need to go one box bigger
              if(result["maxValue"] == 0){
                  // reset the boxSize
                  boxSize = 0;
                  boxes.forEach(function(v,i,a){
                      //console.log(boxSize);
                      // we only want to pick the first bigger size
                      if(v &gt;= total &amp;&amp; boxSize == 0){
                          //console.log(v);
                          boxSize = v;
                      }
                  })
  
                  // if we can't find a boxSize, break
                  if(boxSize == 0){
                      break;
                  }
  
                  // rerun knapsack with the new size
                  result = knapsack(items, boxSize);
  
              }
  
              // push the result to the cart
              ret.cart.push(result);
  
              // remove items that were in the knapsack set
              for (let s in result["set"]) {
                  items = removeItem(items, result["set"][s]);
              }
  
              // break if the prevLength == the items.length, it means we are in a endless loop
              if(items.length == prevLength){
                  break;
              }
              // push the box we selected to the ret value
              (boxSize in ret.boxes) ? ret.boxes[boxSize] = ret.boxes[boxSize] + 1 : ret.boxes[boxSize] = 1;
  
              // reset the prevLength
              prevLength = items.length;
          }
  
          return ret;
  
      }
  
  
  const lengths = [1, 1, 2, 3, 4, 5, 6, 7, 5, 4, 3, 2];
  const boxes = [10, 5, 20];
  const ret = main(lengths, boxes);
  JSON.stringify(ret);
  </code></pre>