Parabolic knapsack

I cooked up a solution in JavaScript using processing.js and HTML5 canvas.

This project should be a good starting point if you want to create your own solution. I added two algorithms. One that sorts the input blocks from largest to smallest and another that shuffles the list randomly. Each item is then attempted to be placed in the bucket starting from the bottom (smallest bucket) and moving up until it has enough space to fit.

Depending on the type of input the sort algorithm can give good results in O(n^2). Here’s an example of the sorted output.

Here’s the insert in order algorithm.

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

Project on github – https://github.com/gradbot/Parabolic-Knapsack

It’s a public repo so feel free to branch and add other algorithms. I’ll probably add more in the future as it’s an interesting problem.