算法来查找不同长度电缆所需的盒子数量

Question

鉴于有人可以购买10K，5K，2K，1K英尺的电缆。

假设它们有 100 个不同长度的电缆落差。

我想确定他们需要购买的最佳组合盒 尽量减少浪费的电缆数量以产生其跌落。

这样做的最佳方法是什么？我不擅长算法:(

我正在尝试完成的简化示例：

您有以下电缆长度：

1， 1， 2， 3， 4， 5，6， 7， 5， 4， 3， 2

您有以下箱子尺寸：

5、10、20

考虑到电缆长度，为了尽量减少浪费，您需要购买：

2 x 20 盒

1 x 5 盒

---

20 = 7， 3， 6， 4

20 = 5， 5， 2， 3， 4， 1

5 = 1， 2

====

=======================================只是为了将来需要这样的东西的其他任何人。这是原始问题的完整代码。这是一个弗兰肯斯坦，通过剪切、粘贴和粘合我发现的不同解决方案，尽管它适用于我的盒子😂。我要再次感谢@bryan60这个解决方案的初始部分，你做了出色的工作，真正帮助这个解决方案开始了。

"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 < numItems + 1; idxItem++) {
weightMatrix[idxItem] = new Array(capacity + 1);
keepMatrix[idxItem] = new Array(capacity + 1);
}
// Build weightMatrix from [0][0] -> [numItems-1][capacity-1]
for (idxItem = 0; idxItem <= numItems; idxItem++) {
for (idxWeight = 0; idxWeight <= 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 <= idxWeight) {
newMax = items[idxItem - 1].b + weightMatrix[idxItem - 1][idxWeight - items[idxItem - 1].w];
oldMax = weightMatrix[idxItem - 1][idxWeight];
// Update the matrices
if (newMax > 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] -> [1][?])
// to create solutionSet
idxWeight = capacity;
idxItem = numItems;
for (idxItem; idxItem > 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"] && !found) {
items.splice(i, 1);
found = true;
}
});
//console.log(items, "items:after");
return items;
}
function getTotal(items){
var s = items.reduce((a,b) => 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 ) => a + b, 0 );
// sort boxes ascending
boxes = boxes.sort((b1, b2) => 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 > 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 <= 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 >= total && 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);

Answer 1

Set L = sum of lengths
While L > 0
Get largest box B where size S <= L OR smallest box
set numB = Floor division L / B OR 1
store numB of B
Subtract numB * B from L

对于可能有浪费的情况，您需要进行一些调整(即需要 4 英尺的电缆，但最小的盒子是 5 英尺)

如果我要做JavaScript：

function getBoxes(lengths, boxes) {
// sort descending
boxes = boxes.sort((b1, b2) => b2 - b1); 
// get the smallest box (needed later)
const minB = boxes[boxes.length - 1]; 
// create an object to store my results;
const boxResult = boxes.reduce((acc, b) => Object.assign(acc, {[b]: 0}), {});
// sum lengths
let L = lengths.reduce((sum, l) => sum += l, 0);
while (L > 0) {
// get first box less than or equal to L or smallest box
const B = boxes.find(b => b <= L) || minB;
// get floor division or 1
const numB = Math.floor(L / B) || 1;
// store that number of that box (adding for waste case)
boxResult[B] += numB;
// subtract from L
L -= numB * B;
}
// done
return boxResult;
}
const lengths = [1, 1, 2, 3, 4, 5, 6, 7, 5, 4, 3, 2];
const boxes = [10, 5, 20];
const result = getBoxes(lengths, boxes);
console.log(result);