Hi there,
I know that I might be very wrong here as I don't understand Math well enough...
For several years I was working on and off on an Optimal Bin Packing Algorithm and was finally able to solve the problem (with approximation of course) without sorting or using combinatorics for more than the first two images.
So my question is if I'm not using combinatorics to solve the problem does it still perform in NP?
Here is a video I made while ago:
Experimenting With Optimal Bin Packing Algorithms Video1
And Here are the steps I use:
1. Get the smallest square based on the first two images
2. Find the best bin (that should be the one that the image will fill the most)
2.1 Measure the new square each time you're testing a bin.
3. Place the image in the given bin and redefine the square if necessary
4. Split bins that overlap with the image
What I have tried:
Here is part of the Photoshop automation code in JavaScript
function findBin(bins, image) {
var x2 = rightBoundary + image.width();
var y2 = bottomBoundary + image.height();
var rightBin = { x1: rightBoundary, y1: 0, x2: x2, y2: y2, ind: 2, num: ++binNum, split: false, type: "right", from: "addRight" };
var bottomBin = { x1: 0, y1: bottomBoundary, x2: x2, y2: y2, ind: 3, num: ++binNum, split: false, type: "bottom", from: "addBottom" };
bins.push(rightBin, bottomBin);
var bestFit = false;
var fitNum = -1;
while (bestFit === false) {
fitNum++;
bestFit = makeFit(bins[fitNum], image);
}
var fits = [bestFit];
fits[0].ind = fitNum;
for (var ind = fitNum + 1; ind < bins.length; ind++) {
var bin = bins[ind];
if (bestFit !== fits[fits.length - 1]) {
bestFit = fits[fits.length - 1];
}
var fit = makeFit(bin, image);
if (fit !== false) {
fit.ind = ind;
if (fit.square < bestFit.square) {
fits.push(fit);
}
else if (fit.square === bestFit.square) {
if (fit.resultDimension < bestFit.resultDimension) {
fits.push(fit);
}
else if (fit.resultDimension === bestFit.resultDimension) {
if (fit.y1 < bestFit.y1) {
fits.push(fit);
}
else {
if (fit.x1 < bestFit.x1) {
fits.push(fit);
}
}
}
}
}
}
bestFit = fits[fits.length - 1];
var bestBin = bins[bestFit.ind];
bestBin.square = bestFit.square;
return bestBin;
}