# Number partitioning targeting ratio of subset sums and equal size

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.

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.

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.