#javascript #arrays #algorithm
#javascript #массивы #алгоритм
Вопрос:
Проблема, которую я пытаюсь решить, заключается в том, что у нас есть части, которые нам нужно вырезать, и мы хотим найти наиболее эффективный способ сделать это.
var lengthsArray = [20, 24, 40, 48];
var piecesNeeded = 8;
var lengthPerPiece = 11.75;
Наиболее эффективный способ сделать это — использовать либо 2 из 48 длин, либо 4 из 24 длин. Как бы я написал функцию для этого? Разные сценарии будут иметь разные значения в lengthsArray.
Я пробовал следующее, но я далеко от базы:
let materialLengthsArray = [48, 40, 24, 20]
let totalLFSF = 94
let materialToBuy = totalLFSF;
let materialsBreakdown = [];
for (i = 0; i < materialLengthsArray.length; i ) {
if(materialToBuy / materialLengthsArray[i] < 1) {
console.log('dun')
} else {
console.log(materialToBuy)
materialsBreakdown.push({
'length' : materialLengthsArray[i],
'count' : Math.floor(materialToBuy / materialLengthsArray[i])
})
materialToBuy = materialToBuy % materialLengthsArray[i]
}
console.log(materialsBreakdown)
console.log('--')
}
Комментарии:
1. На SO, ваш вопрос, вероятно, будет более уважаемым, если вы могли бы показать нам, какие усилия вы приложили, чтобы найти решение — тогда мы могли бы рассказать вам, где вы могли бы улучшить свои идеи.
2. @Cat Я добавил свою печальную попытку. Спасибо! 🙂
Ответ №1:
Вы могли бы вычислить количество остатков / отходов, которые будут поступать из каждой части, и отсортировать их, чтобы найти минимум. Что-то вроде этого?
// sample data
const lengths = [20, 24, 40, 48];
const piecesNeeded = 8;
const pieceLength = 11.75;
// how many pieces of a given length can we get from each unit of material?
const piecesPerItem = (materialLength, pieceSize) => Math.floor(materialLength / pieceSize);
// compute stats for cutting pieces
// from a given denomination of material
const computeWaste = (materialLength, pieceSize) => {
// pieces per unit of material
const perItem = piecesPerItem(materialLength, pieceSize);
// if the piece size is greater than the material size, bail
if (perItem < 1) {
return null;
}
// how many units of material would we need?
const itemsNeeded = Math.ceil(piecesNeeded / perItem);
// how much would be left over from each?
const wastePerItem = materialLength % pieceSize;
// return what we've learned
return {
perItem,
itemsNeeded,
materialLength,
wastePerItem,
totalWaste: wastePerItem * itemsNeeded
};
}
// compute the waste for each material length
const leftovers = lengths.map(length => computeWaste(length, pieceLength));
// sort by least total waste
leftovers.sort(({totalWaste: a}, {totalWaste: b}) => a - b)
// the first entry has the least total waste
console.log(leftovers[0]);
// emit all the results for inspection
console.log(leftovers); Комментарии:
1. Я смотрел на свой экран, пытаясь понять, как оценить эффективность, когда увидел, что ваш ответ пришел. Это идеально. Спасибо.
2. Немного почистил его и добавил несколько комментариев. Обратите внимание, что сортировка будет прервана, если одна из длин слишком короткая . Это легко исправить, но для простоты опущено. Вы также можете настроить его так, чтобы он предпочитал более длинные длины для эквивалентного общего количества отходов, чего вы могли бы достичь, отсортировав массив material lengths в порядке убывания.
3. Это хорошо. Я довольно долго возился с этим, чтобы закончить свой ответ, который делает в основном то же самое, используя ЕЩЕ много строк кода. Стыдно, сколько бедных маленьких электронов я потратил впустую.
Ответ №2:
Это решение вызывает calculateWaste функцию для каждой возможной начальной длины, отображает результаты в параллельный массив и выбирает начальные длины с индексами, которые соответствуют индексам с наименьшими потерями.
calculateWaste Функция использует два вложенных цикла для продолжения вырезания кусков из досок заданной начальной длины до тех пор, пока не будет вырезано достаточное количество досок, а затем возвращает накопленные отходы со всех досок.
const
// Defines starting data
pieces = 8,
length = 11.75,
availableStartingLengths = [20, 24, 40, 48],
// Makes an array of waste amounts for each starting length
amountsWasted = availableStartingLengths.map( (startLen) =>
calculateWaste(pieces, length, startLen)),
// Gets the minimum waste from the new array
minWaste = Math.min(...amountsWasted);
// Gets starting lengths with minimum waste
const bestStartingLengths = amountsWasted.reduce( (indices, amount, index) =>
// Populates an array with the index values having minimum waste
amount === minWaste
? indices.concat(index)
: indices,
[]
// Makes an array of startingLengths at the selected indices
).map(i => availableStartingLengths[i]);
// Reports results
console.log("best starting lengths:", bestStartingLengths);
// Defines the `calculateWaste` function
function calculateWaste(piecesNeeded, lengthPerPiece, startingLength){
//console.log("n" `calculating waste for starting length ${startingLength}`);
let // Defines variables that change in the outer loop
totalPiecesCut = 0,
quantityUsed = 0,
accumulatedScrap = 0;
if(startingLength < lengthPerPiece){ // Board is too short
return Infinity;
}
while(totalPiecesCut < piecesNeeded){
// Starts cutting a new board
quantityUsed ;
let // Defines variables that change in the inner loop
piecesCut = 0,
remaining = startingLength;
while((remaining >= lengthPerPiece) amp;amp; (totalPiecesCut < piecesNeeded)){
//console.log(` cutting ${lengthPerPiece} from ${remaining}`);
// Cuts a new piece
remaining -= lengthPerPiece;
piecesCut ;
}
totalPiecesCut = piecesCut;
accumulatedScrap = remaining;
//console.log(` ${piecesCut} pieces cut from board #${quantityUsed}, with ${remaining} remaining`);
}
//console.log(` ${totalPiecesCut} pieces cut, ${accumulatedScrap} units wasted`)
return accumulatedScrap;
}