Searching for the right partitions

Question

I have a set of integers $U$ with cardinality $311$ and whose sum is 500 dollars.

I want to group all the elements of this set into three different subsets:

• The sum of the elements of subset $A$ is $450$ dollars.

• The sum of the elements of subset $B$ is $30$ dollars.

• The sum of the elements of subset $C$ is $20$ dollars.

What kind of algorithm could provide me a way to find the correct partitions?

What kind of tool could I use to find the vectors of solution? MS Excel is not capable of solving so many decision variables, even if they're integers. Thank you very much!

Answer 1

Let $b=(450,30,20)$. Let binary decision variable $x_{i,j}$ indicate whether element $i$ appears in set $j$. The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ \sum_i i x_{i,j} &= b_j &&\text{for all $j$} \end{align}