Parabolic knapsack

Question

Lets say I have a parabola. Now I also have a bunch of sticks that are all of the same width (yes my drawing skills are amazing!). How can I stack these sticks within the parabola such that I am minimizing the space it uses as much as possible? I believe that this falls under the category of Knapsack problems, but this Wikipedia page doesn't appear to bring me closer to a real world solution. Is this a NP-Hard problem?

In this problem we are trying to minimize the amount of area consumed (eg: Integral), which includes vertical area.

Answer 1

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.