Modified Coin Exchange Problem when only one coin of each type is available

1
votes

Given a total set of denominations and a total amount, we have to find the minimum number of coins needed to make the total exactly.

Constraint: Only one coin of each denomination is available.

How do you compare the Greedy Approach with Dynamic Programming Approach?

Edit: Example: I have cash of denominations 1,2,3,5. I have only one coin of each denomination. I want to get the change for 11 using minimum number of coins. The answer is 4 ( 1 + 2 + 3 + 5). Had I had an infinite supply of each denomination, the answer would've been 3 (5 + 5 + 1 or 5 + 3 + 3).

2
algorithmdynamic-programminggreedy
It isn't clear what specific problem you have. – n. 1.8e9-where's-my-share m.
@ChocoLite Can you explain it more elaborately, probably using examples? – Shudipta Sharma
@n.'pronouns'm. I have added an example for clarification. – ChocoLite
@ChocoLite Is it always possible to make the total? – Shudipta Sharma
@ShudiptaSharma We can assume that the total amount can be achieved by summing different denominations we have. – ChocoLite

2 Answers

2
votes

How do you compare the Greedy Approach with Dynamic Programming Approach?

Greedy approach would fail in your case, because you will never know when to skip or take the coin to get best answer. You have to try all possible solutions by including/excluding each coin.

You can do that using dynamic programming using the same coins change algorithm but avoiding taking same coin more than once, for example

recursive top to bottom approach:

int n = 4, k = 11;
int dp[4][12], coins[] = {1, 2, 3, 5};

int solve(int i = 0, int sm = k) {
    // base case for when the sum is reached
    if (sm == 0) {
        return 0;
    }
    // took more than needed coins or reached the end without reaching sum
    if (sm < 0 || i == n) {
        return 1000000000;
    }
    // check if dp value already calculated
    int& ret = dp[i][sm];
    if (~ret) {
        return ret;
    }
    // otherwise, try taking the coin or skipping it
    return ret = min(solve(i+1, sm), 1 + solve(i+1, sm-coins[i]));
}
int main() {
    memset(dp, -1, sizeof dp);
    cout << solve() << endl;
 return 0;
}
// output: 4
2
votes

Finding any solution, let alone the largest solution, is known as the subset sum problem. It is NP-complete, and the most efficient known algorithms have exponential running time.

Therefore, a greedy algorithm will not work for this problem. You will not do much better than some kind of backtracking search. The solution using dynamic programming will practically be equivalent to a backtracking search, just implemented differently. So the comparison is very short: greedy won't work, but dynamic programming can.