The task is to design an algorithm that partitions the numbers (a₁, a₂, .... ,a_n) in the same order as they appear in the array into the following partitions:

A₁= (a₁, .... , a_j), A₂= (a_{j 1}, .... ,a_k), A₃= (a_{k 1}, .... ,a_c), ..... , A_i= (a_{l 1}, .... ,a_n)

Where the sum of the numbers in each partition cannot go above a certain threshold X and the remainders of the subtraction between X and the sum of the numbers in each partition are all as close to each other as possible. In other words, the values of (X - ∑A₁), (X - ∑A₂), .... , (X - ∑A_i) are all as close as possible.

Example: Say we have the array B= [10,4,5,15,6] and the threshold X= 21. This means that the optimal partitions are [10,4,5] and [15,6] where the sum of the first partition is 19 and the sum of the second partition is 21. In this example, the difference between 19 (Sum of the first partition) and X=21 is 2, and the difference between 21 (Sum of the second partition) and X=21 is 0. So we have the differences as [2, 0]. And this is as close as you can get to minimizing that difference

My Question: How should I approach this? And is there a name for this type of problem that is commonly known among the designing algorithms techniques and problems. I am confident that this problem is solved through dynamic programming with some kind of bottom-up approach. But is there a popular name for this problem that can be looked at as a reference to help me solve this problem.

CodePudding user response：

I tried to implement this algorithm (in Javascript so it can run directly here). I use a for loop with a sum counter to check for each number if we are above X, if yes I created a new list and reset counter.

const example = [10, 4, 5, 15, 6];
const X = 21;
const result = [[]];

let sum = 0;
let listsCounter = 1;
for (const number of example) {
    if (sum   number <= X) {
        result[listsCounter - 1].push(number);
        sum  = number;
    } else {
        result.push([number]);
        sum = number;
        listsCounter  = 1;
    }
}

console.log(result);

CodePudding user response：

A common approach for this kind of problem is the branch-and-bound strategy (see Wikipedia). The idea is to generate (often recursively) the tree of all possible solutions using features of the problem, so-called bounds, to prune away dead-end branches.

The problem requires the differences [(X - ∑A1), (X - ∑A2), ...., (X - ∑Ai)] to be "as close as possible." One way to express this is by mimicking the variance function from statistics,

Variance(partitioning) = ((X - ∑A1)^2 (X - ∑A2)^2 .... (X - ∑Ai)^2) / N

Here N is the number of partitions. The partitioning with the lowest variance is the winner.

During the branch-and-bound search, we would build all possible partitionings recursively to find the one with the minimum variance. We could save the complete partitioning with the lowest variance so far. We may use it as a bound, discarding any incomplete partitioning with a higher variance. To make the bound efficient, we would want to find a complete partitioning with the lowest possible variance as soon as possible. That suggests depth-first searching, favoring partitionings with large (equals few) partitions.