我試圖將給定的陣列分成三個總和幾乎相同的陣列。我設法將陣列分開，但我不確定如何將總和考慮在內。
示例：輸入陣列：[8, 1, 5, 2, 4, 1, 9, 8]
輸出：
[9, 2, 1, 1] // 13
[8, 4] // 12,
[8, 5] // 13
我現在擁有的代碼：
const items = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const n = 3
const result = [[], [], []]
const x= Math.ceil(items.length / 3)
for (let line = 0; line < n; line ) {
for (let i = 0; i < x; i ) {
const value = items[i line * x]
if (!value) continue
result[line].push(value)
}
}
console.log(result);uj5u.com熱心網友回復：
使用陣列存盤物件和陣列 sums 陣列來存盤和跟蹤陣列和：
let arrSorted = {"arr1": [], "arr2": [], "arr3": []}; // storage object
let arrSums = [[0, "arr1"],[0, "arr2"],[0, "arr3"]]; // sums and sort
在回圈源arrSource.forEach陣列（arrSorted_最低電流總和：valsortarrSums
const arrSource = [8, 1, 5, 2, 4, 1, 9, 8];
let arrSorted = {"arr1": [], "arr2": [], "arr3": []};
let arrSums = [[0, "arr1"],[0, "arr2"],[0, "arr3"]];
arrSource.forEach(function (val) {
arrSums.sort(function(a, b){return a[0] - b[0]});
let arr = arrSums[0][1]; // get name of array with lowest sum
arrSorted[arr].push(val);
arrSums[0][0] = val; // update sums array
});
console.log(arrSums, arrSorted);uj5u.com熱心網友回復：
一種方法是：以 (total_sum/3) 作為最大重量運行背包。運行 2 次，然后平均分配余數 - 除以 3 時的最大余數為 2。因此最多有兩個元素剩余，每個元素為 1。
在你第一次運行背包后，移除你找到的物品，然后在剩余的物品上再運行一次背包。之后，您將有兩個麻袋。總共三個麻袋并將剩余的“2”分配給任何麻袋。
uj5u.com熱心網友回復：
當您在評論中寫下您對“合理”的解決方案感到滿意時，我將設定為解決方案應最小化最大垃圾箱大小的目標。這不一定代表理論上的最佳解決方案，因為其他箱仍然可能比它們在最佳解決方案中的潛在偏差更大。
一種蠻力方法可以如下作業：
- 將第一個值放入其中一個箱中。通過以下方式限制 bin 的選擇：
- 如果 bin 的大小已經是要分配的總值的三分之一（或更多），請跳過此 bin。繼續向已經擁有總價值三分之一的垃圾箱添加任何幫助都無濟于事。
- 如果將值添加到 bin 中會使它大于我們在潛在解決方案中作為最大 bin 得到的值，那么也跳過這個 bin：它總是會導致比我們顯然已經找到的分布更差的分布。
- 如果 bin 與已用于此值的其他 bin 之一具有相同的當前大小，則跳過此 bin - 這將導致相同的結果
- 對于可以放置此值的每個 bin：放置它，然后使用遞回以類似的方式將其他值放置在 bin 中。
- 當所有值都已分發時，遞回停止。這是一個候選解決方案。看看最大的垃圾箱是什么。如果這比我們迄今為止發現的要小，那就讓它成為迄今為止最好的解決方案。
- 如果我們很幸運，并且最大的 bin 占總價值的三分之一（向上舍入），那么我們知道我們永遠找不到具有較小最大 bin 的解決方案，因此我們無需進一步研究就可以擺脫遞回。
這是一個實作：
function splitInThree(arr) {
let max = arr.reduce((a, b) => a b, 0);
const oneThird = Math.ceil(max / 3);
const assignment = Array(arr.length).fill(0);
const sums = [0, 0, 0];
function recur(i) {
let improved = false;
if (i < 0) { // All values have been assigned
let currentMax = Math.max(...sums);
improved = currentMax < max;
max = Math.min(max, currentMax);
} else {
const value = arr[i];
let currentMax = max;
for (let bin = 0; bin < 3; bin ) {
// If bin has already a third of the value, or adding the value to it would exceed
// the maximum size we already have a solution with, or if this bin has the same size
// as a previous bin, then skip this bin.
if (sums[bin] >= oneThird || sums[bin] value > max || sums.indexOf(sums[bin]) < bin) continue;
sums[bin] = value;
if (recur(i - 1)) { // Found a better solution
improved = true;
assignment[i] = bin;
if (max === oneThird) break; // We'll take this solution
}
sums[bin] -= value;
}
}
return improved;
}
recur(arr.length - 1);
// Distribute values according to collected assignments
return assignment.reduce((acc, bin, i) => {
acc[bin].push(arr[i]);
return acc;
}, [[], [], []]);
}
// Demo run
let arr = [8, 1, 5, 2, 4, 1, 9, 8];
let result = splitInThree(arr);
console.log(result);轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/490968.html
標籤：javascript 算法
上一篇：添加2個物件串列并從最終串列中洗掉重復的（除了一個欄位不同）元素
下一篇：AWSRDS優化記憶體與突發實體