CODEWITHSUNDEEP
carraysdynamic-programmingpartitioning
Supercan
Supercan

Reputation: 305

Three prong partition (Dynamic Programming example)

I have an array of int which contains numbers like {47, 94, 79, 90, 89, 14, 82, 92}. The array must be divided into three sub-arrays so that the sum of each array is the smallest possible, aka minimal. I think the its worth solving using recursion, however the approach escapes me, i also thought of using qsort on the initial array and then dividing it "greedily" but it doesnt work all the time (e.g taking the lowest and highest number and so on).

For example the numbers above would be divided into: 1) {94, 90, 14} 2) {92, 89} 3) {82, 79, 47}

Here the third array contains the highest minimal sum, which is 208. The order of the numbers does not matter. The question is how to fairly divide the numbers into three groups so that they form the lowest sum. Do I have to test all possibilities?

Upvotes: 3

Views: 507

Answers (1)

Codor
Codor

Reputation: 17605

The described problem can be modelled using dynamic programming. We can define a state space as follows.

v[i,t1,t2] := minimal load in partition 3 attainable for items
              in {0,...,i} where the total load in partition 1
              is exactly t1 and the total load in t2 is exactly t2
              if such a load exists and positive infinity otherwise

For the state space, i is in {0,...n}, and t1, t2 are in {0,...,P} where P is the total sum of the items, which is an upper bound for the objective value and is bounded by n*smax where smax is the largest value occuring in the input.

We obtain the following recurrence relation, where the cases basically depend on iteratively chosing for each element into which partition it is assigned, where s_i denotes the size of the i-th item.

v[i,t1,t2] = min { v[i-1,t1-s_i,t2],
                   v[i-1,t1,t2-s_i],
                   v[i-1,t1,t2] + s_i }

The first term in the minimum expression corresponds to assigning item i into the partition 3, the second case corresponds to assigning item i into partition 2 and the third case corresponds to assigning item i into the partition 3. After the state space is filled, the desired result (namely the minimal maximum load of the partition) can be obtained by evaluation of the following expression.

Result = min { max { t1, t2, v[n,t1,t2] : t1, t2 in {0,...,P} } }

In the maximum expression above, t1 would correspond to the load in partition 1, t2 would correspond to the load in partition 2 and the state value v[n,t1,t2] corresponds to the load in partition 3. The running time of the sketched algorithm can be bounded by O(n^3*smax), which is a pseudopolynomial runtime bound. If additionaly the optimal assignment of the items into the partition is desired, either backtracking or auxiliary data structures have to be used.

Note that it seems artificial to give one of the identical partitions a special role as its load is the value of the states while the load of the other partitions is used for the axes of the state space. Furthermore, at first glance, the value of the state might seem to be trivially obtainable as it is simply the remaining total load

sum_{j=1}^{i} s_i - ( t1 + t2 )

but this is not the case, as the above quantity only determines the load in partition 3 if such an assignment actually exists; in the definition of the state space, the usage of positive infinity indicates the nonexistence of such an assignment.

The approach is very similar to the one described here, page 12 ff. In total, the described problem can be seen as a scheduling problem, namely minimization of the makespan of 3 identical parallel machines. In the so-called three-field notation, the problem is denoted as P3||Cmax, which means that the number of machines is not part of the input, but fixed.

Upvotes: 0

Related Questions