Supercan - 4 months ago 29

C Question

I have an array of

`int`

`{47, 94, 79, 90, 89, 14, 82, 92}`

`qsort`

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`

Answer

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.