我试图将给定的数组分成几乎相同的和的3个数组。我设法分离了数组，但我不确定如何考虑总和。
示例:输入阵列:[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);当你在评论中写下你对一个"合理的";解决方案时，我将把解决方案的目标设置为最小化最大的箱子的大小。这并不一定代表理论上的最优解，因为其他箱子仍然可能比最优解更偏离平均值。
一种暴力破解的方法如下:
- 将第一个值放入其中一个箱子中。以以下方式限制垃圾箱的选择:
- 如果该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);一种方法是:以(total_sum/3)作为最大重量运行backpack。运行2次，然后等量分配余数——除以3的最大余数是2。所以最多剩下两个元素每个元素都是1。
在你运行背包第一次后，删除你发现的项目，然后再运行背包一次对剩余的项目。之后你会有两个袋子。总共三个麻袋，并将剩下的"2"分配到任意一个麻袋中。