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

Question

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

Answer 1

As you write in comments that you are satisfied with a "reasonable" solution, I will set as target that the solution should minimise the size of the largest bin. This does not necessarily represent the theoretical optimal solution, as the other bins could still deviate more from the mean than they potentially would in an optimal solution.

A kind of brute force method could work as follows:

• Place the first value in one of the bins. Limit the choice of bins in the following way:
  • If the bin already has a size that is one third of the total value to distribute (or more), skip this bin. It never helps to keep adding to a bin that already has one third of the total value.
  • If adding the value to the bin would make it larger than what we got as largest bin in a potential solution, then skip this bin too: it would always lead to a worse distribution than the one we apparently already found.
  • If the bin has the same current size as one of the other bins that was already used for this value, then skip this bin -- it would lead to the same result
• For each of the bins where this value can be put: put it, and use recursion to place the other values in bins in a similar way.
• The recursion stops when all values have been distributed. This is a candidate solution. See what the largest bin is. If this is smaller than what we had found up till now, make it the best solution so far.
• If we are lucky and the largest bin has one third of the total value (rounded upwards), then we know we could never find a solution that has a smaller largest bin, so we can get out of recursion without looking further.

Here is an implementation:

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

Answer 2

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.