Minimum Cost Difference Partition

You are given a list of positive integers where each integer represents the cost to build a section of a road. Your task is to partition these sections into two groups such that the absolute difference between the total costs of the two groups is minimized.

Formally, given a list of costs \(c_1, c_2, \ldots, c_n\), let \(S = \sum_{i=1}^n c_i\). Find a subset \(A\) such that the sum \(s = \sum_{i \in A} c_i\) is as close as possible to \(S/2\). The two groups then have costs \(s\) and \(S-s\) respectively. The output should list the two sums in ascending order.

Example:

Input: [3, 1, 4, 2, 2]
Total cost = 12, one optimal partition is [3, 1, 2] and [4, 2].
Output: 6 6

This problem can be solved with dynamic programming by finding the maximum sum no more than \(\lfloor S/2 \rfloor\) that can be formed from a subset of the numbers. Use this value to compute the other group’s sum and output the result in sorted order.

inputFormat

The input begins with an integer \(T\) on the first line representing the number of test cases. Each of the following \(T\) lines contains space-separated integers representing the costs for that test case.

For example:

3
3 1 4 2 2
10 20 15 5 5
1 1 1 1

outputFormat

For each test case, output a single line containing two integers separated by a space. These integers represent the two group costs (in ascending order) whose difference is minimized.

For the sample input above, the output would be:

6 6
25 30
2 2

## sample

3
3 1 4 2 2
10 20 15 5 5
1 1 1 1

6 6
25 30
2 2

</p>