0
$\begingroup$

I've just read this article about solving the below minimum subset sum using dynamic programming technique.

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?

  • 2
    I thi$n$k cs.SE is more appropriate.2012-06-28

1 Answers 1

0

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

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.