I'm trying to make a function to solve the bin packing problem with best fit algorithm, but It doesn't output the results I'm expecting.
Here's what I done so far ..
const bestFit = (stringArray, maxWidth) => {
let results = [[]];
stringArray.sort((a, b) => b.length - a.length); // Sort from big to small
// ['TailwindCSS', 'Woocommerce', 'typescript', 'three.js', 'threlte', 'svelte', 'Python', 'CSS']
try {
stringArray.forEach((str, strIndex) => {
if (!results[0][0]) {
results[0].push(str)
} else {
const tempArray = [];
results.forEach((_elm, _idx) => {
tempArray.push({ index: _idx, data: _elm });
});
tempArray.sort((a, b) => {
return a.data.join().length - b.data.join().length; // From small to big
})
for (const [_tx, _obj] of tempArray.entries()) {
const availableSpace = (_obj.data.join('').length str.length) <= maxWidth;
if (availableSpace) {
results[_obj.index].push(str);
continue;
} else {
if (tempArray[_tx 1]) {
continue;
} else {
results.push([str]);
}
}
}
}
});
} catch (e) {
console.log(e);
}
return results;
}
const technologies = ['svelte', 'typescript', 'threlte', 'three.js', 'TailwindCSS', 'Python', 'Woocommerce', 'CSS'];
const MAX_LENGTH = 20;
const results = bestFit(technologies, MAX_LENGTH);
console.log(results);
// [
// ["TailwindCSS", "three.js",],
// ["Woocommerce", "three.js",],
// ["typescript", "three.js",],
// ["threlte", "svelte", "Python",],
// ["svelte", "Python", "CSS",],
// ["Python", "CSS",],
// ["CSS",],
// ]
There's a lot of duplicates and sorting doesn't work well, there's of example the word CSS could be in the first child array, but the function put it in a separate array!
What's wrong here?
CodePudding user response：
I threw this together, I believe it's what you are looking for.
You should try to break your problem down into smaller parts, individual functions that do one thing each and make sure that they work.
In this case I have a few helper functions, chooseBinWithMostSpaceLeft takes the list of bins and figures out which one has the most space left. If no bins have room left, it returns undefined.
Then, in the main function we take that bin with the most space left, and make sure the item will actually fit into it. If it does, great, we add the item, otherwise make a new bin.
We also have to make sure the items themselves aren't too big, that's what my filter does, it checks too make sure the strings aren't bigger than the maximum width.
EDIT: I misread the problem definition and gave the worst-fit solution. Here is the best fit, there was also a bug in my chooseBinWithLeastSpaceLeft function that would result in undefined being returned in some cases even when there were valid bins.
function worstFit(stringArray, maxWidth) {
const willFit = stringArray.filter((str) => str.length <= maxWidth);
willFit.sort((a, b) => b.length - a.length);
const bins = [];
willFit.forEach((str) => {
// find the bin with the most space left in it.
const worstBin = chooseBinWithMostSpaceLeft(bins, maxWidth);
// make sure that bin is not undefined.
// make sure the item fits in that bin.
if (worstBin !== undefined && willBinFit(worstBin, maxWidth, str)) {
// add the item to the bin.
worstBin.push(str);
} else {
// make a new bin with the item in it.
bins.push([str]);
}
});
return bins;
}
/**
* find the bin with the most size left.
* returns undefined if no bins have size left.
*/
function chooseBinWithMostSpaceLeft(bins, maxWidth) {
return bins.reduce((max, bin) => {
const binWidthLeft = getRemainingBinWidth(bin, maxWidth);
if (max === undefined && binWidthLeft > 0) return bin;
// this bin has room left, can use it.
else if (max === undefined && binWidthLeft <= 0) return min;
// this bin doesn't have room left, cannot use it.
else if (binWidthLeft <= 0) return max;
else {
const maxWidthLeft = getRemainingBinWidth(max, maxWidth);
if (binWidthLeft > maxWidthLeft) return bin;
else return max;
}
}, undefined); // start undefined, it is possible there are no bins with room left.
}
// Determine how much space the items in the bin are taking up.
function getBinWidth(bin) {
return bin.reduce((sum, str) => sum str.length, 0);
}
// Determine how much room the bin has left.
function getRemainingBinWidth(bin, maxWidth) {
return maxWidth - getBinWidth(bin);
}
// Determine whether or not the item will fit in the bin.
function willBinFit(bin, maxSize, item) {
return getRemainingBinWidth(bin, maxSize) >= item.length;
}
function bestFit(stringArray, maxWidth) {
const willFit = stringArray.filter((str) => str.length <= maxWidth);
willFit.sort((a, b) => b.length - a.length);
const bins = [];
willFit.forEach((str) => {
// find the bin with the most space left in it.
const bestBin = chooseBinWithLeastSpaceLeft(bins, maxWidth, str);
// make sure that bin is not undefined.
// make sure the item fits in that bin.
if (bestBin !== undefined) {
// add the item to the bin.
bestBin.push(str);
} else {
// make a new bin with the item in it.
bins.push([str]);
}
});
return bins;
}
function chooseBinWithLeastSpaceLeft(bins, maxWidth, str) {
return bins.reduce((min, bin) => {
const binWidthLeft = getRemainingBinWidth(bin, maxWidth) - str.length;
if (min === undefined && binWidthLeft >= 0) return bin;
// this bin has room left, can use it.
else if (min === undefined && binWidthLeft <= 0) return undefined;
// this bin doesn't have room left, cannot use it.
else if (binWidthLeft <= 0) return min;
else {
const minWidthLeft = getRemainingBinWidth(min, maxWidth) - str.length;
if (binWidthLeft < minWidthLeft) return bin;
else return min;
}
}, undefined); // start undefined, it is possible there are no bins with room left.
}
console.log(
"worst",
worstFit(
[
"TailwindCSS",
"Woocommerce",
"typescript",
"three.js",
"threlte",
"svelte",
"Python",
"CSS"
],
23
)
);
console.log(
"best",
bestFit(
[
"TailwindCSS",
"Woocommerce",
"typescript",
"three.js",
"threlte",
"svelte",
"Python",
"CSS"
],
23
)
);