What is the maximal amount of money attained from coins of 1, 5, 10, 25 cent denominations that none of its subset amounts to 100 cents? We can find the solution with exhaustive or naive dynamic programming but I am looking for a clever approach, say a clever dynamic programming algorithm.
What is the general algorithm for the following generalized version of this problem?
$(x_i)_{i=1}^n$ is an n-tuple of natural numbers and $s$ a natural number. Let $A=\big\{(a_i)_{i=1}^n\big|b_i\le a_i \implies\sum_{i=1}^nb_ix_i\ne s,\, b_i\in \overline{\mathbb Z^-}\big\}$. Find $$\max_{(a_i)_{i=1}^n\in A}\sum_{i=1}^na_ix_i$$ and all maximizing non-negative tuples $(a_i)_{i=1}^n$'s.
In this case, where every coin value can be created from other coins with the exception of 25 cents not being created from 10 cent coins, the maximum amount is obviously 1x25 + 9x10 + 4x1. But if we replaced "100 cent" with "99 cent", there would be no limit as long as we don't use four 1 cent coins.
The target amount (here: 100 cent) must be a multiple of each coin value, otherwise we use an unlimited amount of that coin. So it must be a multiple of the LCM of all coin values, here: 50 cent. That also limits how many of each coin we can have; here: 3x25, 9x10, 19x5, 99x1 cent. You can further limit the numbers: If you had 5x1 cent, then changing it for 1x5 cent could only improve things because you would have fewer choices for subsets etc. So you have at most 3x25, 9x10, 1x5, 4x1 cent. We can assume 4 single cents because gcd (25, 10, 5) = 5. That very much reduces your choices.