1
$\begingroup$

Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40)

How would I find the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k?

I believe this algorithm is NP complete.

Just think of the problem as a bin packing algorithm but instead of saying that the total value of items in the bin must not exceed the bin's capcacity, I am saying that the total value of items in the bin must be exactly equal to the bin's capacity. Also, we are trying to maximise the number of bins.

Example scenario:

Say I have a list: [1, 2, 2, 3, 5, 6, 5] and k=7, then some example values of S would be:

[(3+2+2), (6+1)] - 5 and 5 left over

[(5+2), (5+2), (6+1)] - 3 left over

As you can see, the second solution is optimal because it produces 3 partitions rather than 2.

$\endgroup$
1
$\begingroup$

This problem is NP-complete. Even testing whether there exists a single subset that sums to $k$ is NP-complete; that is known as the subset sum problem. Therefore, you should not expect any efficient solution to this problem.

If you are asking for any way to solve it, without regard to efficiency, one approach is to enumerate all possible subsets that sum to $k$, build a graph with an edge between each pair of subsets that are not disjoint, and search for a maximum independent set in this graph. Another approach would be to use integer linear programming; define the zero-or-one $x_{ij}$ integer variable to be 1 if the $i$th subset includes the element $j$, and then add constraints to reflect the problem statement, i.e., $\sum_j x_{ij} j = k$ and $x_{ij} + x_{i'j} \le 1$ for all $i\ne i'$. Then, apply an off-the-shelp ILP solver.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.