Identify problem of computing optimal partition

19 Views Asked by At

I would like to identify the general theory or the formal name for the following type of problem.

Consider a list of integers, denoted as $l$. The goal is to compute the partitions of $l$ into two subsets, such that the absolute value of the difference between the sums of each subset is minimized.

For example, consider $l = \{20, 20, 15, 15, 30\}$. We can partition $l$ into subsets of 3 and 2 elements, as well as 1 and 4 elements. For the partitions of 2 and 3 elements, I found that the minimal difference corresponds to the partition $\{20, 15, 15\}$, and $\{20, 30\}$.

The total of the first and second elements of the partition is 50. Therefore, the absolute value of the difference is zero.

For the partitions of 1 and 4 elements, there is no solution that yields a zero difference.

1

There are 1 best solutions below

0
On BEST ANSWER

This is the optimization variant of the decision problem that is called the subset sum problem. See https://en.m.wikipedia.org/wiki/Subset_sum_problem