Separating array into 3 parts with near the same sum in Javascript-CodePudding

I'm trying to separate the given array into 3 arrays that have almost the same sum. I managed to separate the array, but I'm unsure how to take the sum into considiration.

Example: Input array:[8, 1, 5, 2, 4, 1, 9, 8] Output:

 [9, 2, 1, 1] // 13
 [8, 4] // 12,
 [8, 5] // 13

Code I have now:

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);

CodePudding user response：

Using an array storage object, and an array sums array, to store and keep track of the array sums:

let arrSorted = {"arr1": [], "arr2": [], "arr3": []}; // storage object
let arrSums = [[0, "arr1"],[0, "arr2"],[0, "arr3"]]; // sums and sort

While looping the source array (arrSource.forEach), it is determined which array in the array storage object (arrSorted) ought to get the current value (val), by sort-ing the sums array (arrSums) numerically, then pushing the current value onto the storage array with the lowest current sum:

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);

CodePudding user response：

One approach is : Run knapsack with (total_sum/3) as max weight. Run 2 times and then distribute the remnant equally - the greatest remainder when divided by 3 is 2. So there will be max two elements remaining each one being 1.

After you run knapsack 1st time remove the items you found and then run the knapsack one more time on the remaining items. After that you will have two sacks more. Total three sacks and distribute the remaining '2' among any of the sacks.