1

This is a version of the coin-changing problem. As such, it is a dynamic programming problem.

I know how to determine if you can make change if either you can use at most one coin of each denomination or if you can use at most k coins, but not both.

lars
  • 1,976
  • 5
  • 33
  • 47
  • Yes. I know this. I don't see how to get figure the constraint of k coins into the recurrence. – lars Jan 19 '16 at 21:21
  • @user2357112 "I know how to determine if you can make change if either you can use at most one coin of each denomination or if you can use at most k coins, but not both." ... Interpret this as saying I know this is a variant of the 0-1 knapsack problem, however I don't see how you can combine *all* the constraints. Relatedly, Look at question 3: https://cise.ufl.edu/class/cot5405sp10/exams/Midterm3sol.pdf. You can get very different recurrences depending on your restraints. My question is how you combine all the restraints. – lars Jan 19 '16 at 21:34

2 Answers2

5

Combining the constraints is fairly straightforward. We can build a three-dimensional table with dimensions representing maximum coin allowed, number of coins allowed, and target sum, or we can just say "screw it" and throw memoization on top of a straightforward recursive solution. In Python:

# Assume we have a memoization decorator.
# functools.lru_cache(maxsize=None) would do.
@memoize
def knapsack_possible(coin_tuple, target, k):
    if not target:
        # Target achieved.
        return True
    elif not coin_tuple or not k:
        # Out of coins.
        return False
    else:
        return (knapsack_possible(coin_tuple[:-1], target, k) or
                knapsack_possible(coin_tuple[:-1], target-coin_list[-1], k-1)
user2357112
  • 260,549
  • 28
  • 431
  • 505
  • 1
    I think we can improve may be , Calculating the minimum number of coins required for making a change of target . which can be done as f( n , target ) = min(f(n-1,target) , f(n-1,target - coin[n]) + 1 ) .. Now if we can make a change with <= K coins we can return yes else no! – Shubham Sharma Jan 21 '16 at 08:01
  • @ShubhamSharma: That doesn't let us keep track of which coins we've used, though. – user2357112 Jan 21 '16 at 15:54
  • We can always backtrack and generate the set without affecting the complexity – Shubham Sharma Jan 21 '16 at 16:03
  • @ShubhamSharma: Oh, I see. You're calculating the minimum number of the first n coins (or n+1 depending on indexing convention) we'd need to achieve a sum equal to the target. I thought you were neglecting the constraint against reusing coins. Your recurrence would indeed be superior to the 3D table I proposed, though I think the memoized version makes essentially the same call tree as a memoized version of your proposal. – user2357112 Jan 21 '16 at 17:50
0

wouldn't it be the same as N denominations, but add another final check to ensure N<=k?

changeWithN(amt, k){ ... return n<=k ? n : -1 }

MichaelWClark
  • 382
  • 1
  • 12
  • One way of thinking about this is: how to do you implement the check? And you can you get the check as part of the recurrence? I don't know what changeWithN(amt, k){ ... return n<=k ? n : -1 } is supposed to be doing. I don't know what n is in this scenario. Also, if n is the # of denoms, then you would only look at the first k denoms. – lars Jan 19 '16 at 21:32
  • can you give me some suedo code or something for the other solutions? I might be able to assist better then. You said you can solve for n or solve for k, show me those so i can see what your doing and maybe able to see how to combine. – MichaelWClark Jan 19 '16 at 21:35
  • Maybe this will help: https://cise.ufl.edu/class/cot5405sp10/exams/Midterm3sol.pdf Look at Q3 part a,c. – lars Jan 19 '16 at 21:36