Change a coin (dynamic programming)

Question

I have a question about the problem of changing coins, when we need to not only print the number of ways to change $ n with the data of coin denominations, for example, {1,5,10,25}, but also print the paths

For example, if the goal = $ 50, and the coins - {1,5,10,25}then the ways to actually use coins to get the goal

• 2 × $ 25
• 1 × $ 25 + 2 × $ 10 + 1 × $ 5
• and etc.

What is the best time complexity we could solve to solve this problem? I tried to change the dynamic programming solution for the coin change problem, where we only need the number of ways, but not the actual ways

It’s hard for me to understand the complexity of time. I use memorization, so I don’t need to solve the same problem again for a given coin amount and amount, but we still need to sort through all the solutions and print them. So the time complexity is definitely greater than O (ns), where n is the number of coins and s is the target. Is it exponential? Any help would be greatly appreciated

Answer 1

Print Combinations

def coin_change_solutions(coins, S):
  # create an S x N table for memoization
  N = len(coins)
  sols = [[[] for n in xrange(N + 1)] for s in xrange(S + 1)]
  for n in range(0, N + 1):
    sols[0][n].append([])

  # fill table using bottom-up dynamic programming
  for s in range(1, S+1):
    for n in range(1, N+1):
      without_last = sols[s][n - 1]
      if (coins[n - 1] <= s):
          with_last = [list(sol) + [coins[n-1]] for sol in sols[s - coins[n - 1]][n]]
      else:
          with_last = []
      sols[s][n] = without_last + with_last

  return sols[S][N]


print coin_change_solutions([1,2], 4)
# => [[1, 1, 1, 1], [1, 1, 2], [2, 2]]

• without : we don’t need to use the last coin to make the amount. All coin solutions are found directly by recursing onto solution[s][n-1]. We take all these combinations of coins and copy them to with_last_sols.

• : . . sol[s - coins[n - 1]][n]. , . sol coin[n - 1]:

   

  # For example, suppose target is s = 4
  # We're finding solutions that use the last coin.
  # Suppose the last coin has a value of 2:
  #
  # find possible combinations that add up to 4 - 2 = 2: 
  # ===> [[1,1], [2]] 
  # then for each combination, add the last coin 
  # so that the combination adds up to 4)
  # ===> [[1,1,2], [2,2]]
  

, .

without_last_sols = [[1,1,1,1]]
with_last_sols = [[1,1,2], [2,2]]
without_last_sols + with_last_sols = [[1,1,1,1], [1,1,2], [2,2]]

---

1 n:  = [1,2,3,4,..., n] - , num , s, p (s). , p (s) .
, = p (s) = O (2 ^ s). , . , .

: s n.
s n sols[s][n]:

• : O (2 ^ s) sol[s - coins[n - 1]][n]. O (n) . , O (n × 2 ^ s).
• : O (2 ^ s) sol[s][n]. sol O (n) , . O (n × 2 ^ s).

, O (s × n) × O (n2 ^ s + n2 ^ s) = O (s × n ^ 2 × 2 ^ s).

---

- O (s × n ^ 2 × 2 ^ s), s × n , O (2 ^ s) (, [[1, 1, 1, 1], [1, 1, 2], [2, 2]]), (, [1,1,1,1]) O (n) .

Answer 2

d_i - , . d_i = {1, 5, 10, 25}. k - (), k = 4.

numberOfCoins [1..k] [0..n], , . :

numberOfCoins[k][n] = min(numberOfCoins[i − 1][j], numberOfCoins[i][j − d_i] + 1)

, d_i, ( ):

numberOfCoins[i][j] = numberOfCoins[i − 1][j]   // eq1

d_i, +1 d_i ( ):

numberOfCoins[i][j] = numberOfCoins[i][j − d_i] + 1   // eq2

O (kn), , k , , O (4n) = O (n).

2D-, coinUsed, , numberOfCoins, , . , coinUsed [i] [j], "^" ( eq1). , "<" ( eq2).

. , - O (kn).

, , , k + n + 1 . , 1 . , , O (kn) + O (k + n + 1). , k , O (kn) + O (k + n + 1) = O (kn) + O (n + 1) = O (kn) + O (n) = O ((k +1) n) = O (n).

Answer 3

, , , memoization.

, , .

, , , , . :

void print(vector<int>& coinsUsed)
{
    for(auto c : coinsUsed)
    {
        cout << c << ",";
    }
    cout << endl;
}

int helper(vector<int>& coins, int target, int index, vector<int>& coinsUsed)
{
    if (index >= coins.size() || target < 0) return 0;

    if (target == 0)
    {
        print(coinsUsed);
        return 1;
    }

    coinsUsed.push_back(coins[index]);
    int with = helper(coins, target - coins[index], index, coinsUsed);

    coinsUsed.pop_back();
    int without = helper(coins, target, index + 1, coinsUsed);

    return with + without;
}

int coinChange(vector<int>& coins, int target)
{
    vector<int> coinsUsed;
    return helper(coins, target, 0, coinsUsed);
}

:

vector<int> coins = {1,5,10,25};
cout << "Total Ways:" << coinChange(coins, 10);

Thus, this gives you the total number of ways, as well as the coins used in the process to achieve the goal stored in coinsUsed, now you can save this as soon as possible by storing the transferred values ​​in the cache.

The time complexity of a recursive solution is exponential.

Link to the current program: http://coliru.stacked-crooked.com/a/5ef0ed76b7a496fe