I have a very long "list" of numbers ( maybe thousands ) which may be grouped, by sum into "n" groups. The number of groups and values are given. For example:
I need to find a summary of which numbers in the "list" will crate given "groups".
Ideas?
You can solve the problem via integer linear programming as follows. Let binary decision variable $x_{i,g}$ indicate whether item $i$ (with value $v_i$) appears in group $g$. Let $s_g$ be the target sum for group $g$. The problem is to find a feasible solution to the linear constraints \begin{align} \sum_g x_{i,g} &= 1 &&\text{for all $i$} \\ \sum_i v_i x_{i,g} &= s_g &&\text{for all $g$} \end{align}
This looks like a variation of The Subset Sum Problem Given a list of numbers, does some subset's sum equal 0? The complexity remains the same if the target isn't zero.
A brute force algorithm is loop through the desired targets generating subsets, then add each subset's terms. There are $2^N-1$ possible subsets if you ignore the empty set. You can generate the subsets by generating the first $2^N-1$ binary numbers, and have a routine that can convert the number into its corresponding sum. $1$ means include, $0$ means exclude.
You probably don't want to use this method for 1000 data points. That article has some alternatives.
