Number partitioning targeting ratio of subset sums and equal size

Question

I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get approximate answers. However, I am looking to split a set into 2 subsets of minimum difference in size but with a target ratio of sums.

I have tried variations of greedy algorithms that will work to minimize the largest difference of the two metrics at any point in the calculation, but this just results in a result that splits the difference between the two. I'm happy with an approximate solution since it needs to run in a reasonable amount of time.

Answer 1

The problem is NP-hard (assuming the numbers are represented in binary). If you could solve your problem efficiently, you could solve the Partition problem: Partition is the special case where the minimum difference is zero (and the target ratio is 1:1). Therefore, you should not expect any simple algorithm to be both efficient and always correct.

If you want a heuristic that gives an approximation, greedy algorithms are reasonable. I suggest you try adapting the standard algorithms for the Partition problem. Another approach is to use an integer linear programming solver.

Answer 2

As D.W.'s answer mentions, this is NP-hard to solve exactly as a known NP-hard problem is a special case of it.

To adapt any algorithm (exact or heuristic) for solving the Partition Problem to your problem, just add a single new "dummy" number calculated to make the ratio what you want. Suppose you want one of the sides to have sum $r$ times the other side's sum, and the total of all numbers is $t$. Since PP finds equal-sum partitions, we want to find a number $d$ to add such that $x+d=rx$, so that removing $d$ leaves us with a sum $x$ on one side, and $rx$ on the other side. Additionally we have that $x+d=rx=(t+d)/2$. We want to eliminate the unknown $x$ and rearrange to obtain $d$ in terms of the other, known, parameters:

$$ x+d=rx\\ x-rx=-d\\ x(1-r)=-d\\ x=d/(r-1) $$

Substituting this into $rx=(t+d)/2$ gives

$$ rd/(r-1)=(t+d/(r-1))/2\\ 2rd=t(r-1)+d\\ d(2r-1)=t(r-1)\\ d=t(r-1)/(2r-1) $$

The PP algorithm will assign this number to one of the two sides; afterwards, just discard it.