<p>The problem is a generalization of the <a href="http://en.wikipedia.org/wiki/Set_packing" rel="nofollow">set packing problem</a> (exercise: why?), and therefore it is NP-hard even to approximate in a very weak sense.  See <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node144.html" rel="nofollow">Maximum Set Packing</a> and <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node33.html" rel="nofollow">Maximum Clique</a> in the compendium.</p>

CC BY-SA 3.0
2012-10-22T21:07:02.410Z
2012-10-22T21:07:02.410Z
Tsuyoshi Ito
<p>Try researching <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow">dynamic programming</a>.  Dynamic programming provides the ability to iterate over a problem set that involves multiple equations.  Also, take a look at <a href="http://en.wikipedia.org/wiki/Gaussian_elimination" rel="nofollow">gaussian elimination</a>.</p>

<p>If properly designed and implemented by setting the data up properly, gaussian elimination can intelligently reduce the number of combinations that the algorithm will need to look at.  In your example, a limit of 12 j was specified.  So, if one of the combinations looked at is 12 of A (which consists of i + j + k), then both i and j are exhausted since there are only 12 of each.  So, any other combination that uses i or j (like D which uses 2 of j) no longer needs to be evaluated since we know that this combination can not be used.</p>

CC BY-SA 3.0
2012-10-21T17:16:38.160Z
2012-10-21T17:16:38.160Z
Bob Bryan
<p>I have a bit of a problem, I have a set of sums that add up to X, like so:</p>

<p>A: $i + j + k = X$</p>

<p>B: $t + z = X$</p>

<p>C: $z + z = X$</p>

<p>D: $j + j + k + k = X$</p>

<p>I have a limited number of summands so for example I have: 12 of $i$, 35 of $z$, 12 of $j$, and 18 of $k$, 21 of $t$. </p>

<p>What I need is an algorithm that will determine the best way to use those combinations so that I end up with the most complete sums of $X$</p>

<p>So in the example above using:</p>

<p>17 of combination $C$, 1 of combination $B$, and 12 of combination $A$, total 30 sums of $X$, 72 summands used</p>

<p>is worse then using:</p>

<p>21 of combination $B$, 7 of combination $C$, and 6 of combination $D$, total 34 sums of $X$, 80 summands used</p>

<p><em>EDIT</em>:</p>

<p>To further explain:</p>

<p>using 21 of combination $B$ will "spend" 21 $t$ and 21 $z$ leaving us with: 12 of $i$, 14 of $z$, 12 of $j$, 18 of $k$, 0 of $t$</p>

<p>using 7 of combination $C$ will "spend" 14 of $z$ (because it uses 2 summands of $z$ to be achieved) leaving us with: 12 of $i$, 0 of $z$, 12 of $j$, 18 of $k$, 0 of $t$</p>

<p>using 6 of combination $D$ will spend 12 of $j$ and 12 of $k$ (because it uses both of them twice) leaving us with: 12 of $i$, 0 of $z$, 0 of $j$, 6 of $k$, 0 of $t$</p>

<p>we can no longer make combinations that will add up to $X$ thus the algorithm is concluded.</p>

CC BY-SA 3.0
2012-11-12T07:07:15.790Z
The question would be clearer (at least to me) if you gave a general specification, instead of just an example.
Jeffε
CC BY-SA 3.0
2012-10-21T19:42:07.750Z
this sounds like a variant on BIN PACKING, where the goal is to make as many unit size buckets (here X = 1) by combining elements.
Suresh Venkat
CC BY-SA 3.0
2012-10-22T11:23:28.647Z
Kind of a dual goal: here you do not allow slack in the bins, but you are allowed not to pack all objects.
MassimoLauria
CC BY-SA 3.0
2012-10-22T14:38:34.257Z
@SureshVenkat well Bin Packing has similarities to this yes, I would love to use a Bin Packing algorithm if you know of one that will pack the objects in this manner, I don't... ones I know usually pack them imperfectly.
Elijah Vankov
CC BY-SA 3.0
2012-10-22T14:40:25.940Z
@MassimoLauria well yes if we pack all objects we don't get X, however I can easily discard results that don't obtain X if you have a solution that will pack all of them perfectly, but as I mentioned above Bin Packing usually doesn't do that.
Elijah Vankov
<ds.algorithms><co.combinatorics>
Find the optimal way to use combinations of summands to get the most sum with a limited number of summands
Elijah Vankov
# Find the optimal way to use combinations of summands to get the most sum with a limited number of summands

(Asked by: username_0 on 2012-10-21)

I have a bit of a problem, I have a set of sums that add up to X, like so:

A: $i + j + k = X$

B: $t + z = X$

C: $z + z = X$

D: $j + j + k + k = X$

I have a limited number of summands so for example I have: 12 of $i$, 35 of $z$, 12 of $j$, and 18 of $k$, 21 of $t$.

What I need is an algorithm that will determine the best way to use those combinations so that I end up with the most complete sums of $X$

So in the example above using:

17 of combination $C$, 1 of combination $B$, and 12 of combination $A$, total 30 sums of $X$, 72 summands used

is worse then using:

21 of combination $B$, 7 of combination $C$, and 6 of combination $D$, total 34 sums of $X$, 80 summands used

*EDIT*:

To further explain:

using 21 of combination $B$ will "spend" 21 $t$ and 21 $z$ leaving us with: 12 of $i$, 14 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 7 of combination $C$ will "spend" 14 of $z$ (because it uses 2 summands of $z$ to be achieved) leaving us with: 12 of $i$, 0 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 6 of combination $D$ will spend 12 of $j$ and 12 of $k$ (because it uses both of them twice) leaving us with: 12 of $i$, 0 of $z$, 0 of $j$, 6 of $k$, 0 of $t$

we can no longer make combinations that will add up to $X$ thus the algorithm is concluded.

**Tags:** ds.algorithms, co.combinatorics
> **Comments:**
> **username_2**: this sounds like a variant on BIN PACKING, where the goal is to make as many unit size buckets (here X = 1) by combining elements.  
> **username_3**: Kind of a dual goal: here you do not allow slack in the bins, but you are allowed not to pack all objects.  
> **username_0**: @SureshVenkat well Bin Packing has similarities to this yes, I would love to use a Bin Packing algorithm if you know of one that will pack the objects in this manner, I don't... ones I know usually pack them imperfectly.  
> **username_0**: @MassimoLauria well yes if we pack all objects we don't get X, however I can easily discard results that don't obtain X if you have a solution that will pack all of them perfectly, but as I mentioned above Bin Packing usually doesn't do that.  
> **username_1**: The question would be clearer (at least to me) if you gave a general specification, instead of just an example.  

---

## 2 answers

### Answer by username_4 on 2012-10-22. Score: 4

The problem is a generalization of the [set packing problem](http://en.wikipedia.org/wiki/Set_packing) (exercise: why?), and therefore it is NP-hard even to approximate in a very weak sense. See [Maximum Set Packing](http://www.nada.kth.se/~viggo/wwwcompendium/node144.html) and [Maximum Clique](http://www.nada.kth.se/~viggo/wwwcompendium/node33.html) in the compendium.


---

### Answer by username_5 on 2012-10-21. Score: -1

Try researching [dynamic programming](http://en.wikipedia.org/wiki/Dynamic_programming). Dynamic programming provides the ability to iterate over a problem set that involves multiple equations. Also, take a look at [gaussian elimination](http://en.wikipedia.org/wiki/Gaussian_elimination).

If properly designed and implemented by setting the data up properly, gaussian elimination can intelligently reduce the number of combinations that the algorithm will need to look at. In your example, a limit of 12 j was specified. So, if one of the combinations looked at is 12 of A (which consists of i + j + k), then both i and j are exhausted since there are only 12 of each. So, any other combination that uses i or j (like D which uses 2 of j) no longer needs to be evaluated since we know that this combination can not be used.


---

