# How to solve the maximum subset sum problem?

Given a list of $N$ coins, their values $(V_1, V_2, ... , V_N)$, and the total sum S. Find the minimum number of coins the sum of which is $S$ (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to $S$.

How can I use the same technique to find the maximum subset of coins that sums up to $S$? And what is the recurrence relation for this 2nd problem?

-
I think cs.SE is more appropriate. –  Frank Science Jun 28 '12 at 7:04

The pseudocode for minimum subset sum given in the article is as follows:

Set M[i] equal to infinity for all of i
M[0]=0

For i = 1 to S
For j = 0 to N - 1
If (Vj<=i AND M[i-Vj]+1<M[i])
Then M[i]=M[i-Vj]+1

Output M[S]


The inner loop over $j$ is just computing $M[i] := \min\limits_{V_j \le i} M[i-V_j] + 1$. To compute the maximum subset sum, you just have to replace $\min$ with $\max$, which you can do by initializing $M$ to $-\infty$ instead of $\infty$, and changing the less-than sign in the comparison of $M$ to a greater-than sign.

-