Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:
Input: amount = 10, coins = [10]
Output: 1

Note:
You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

This is one variant of the classic knapsack problem where you can use unlimited items of a kind. The target is to find the total number of combinations. Another similar problem is to find the shortest combination: Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm

Unlimite Knapsack Problem via Depth First Search Algorithm to Find All Combination

The most intuitive method is to use the Depth First Search algorithm that makes a choice (choose a coin) and move on to the next by subtracting the coin value from the amount, thus, we have a smaller problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        dfs(amount, coins, 0);
        return ans;
    }
private:
    int ans = 0;
    void dfs(int amount, vector<int>& coins, int idx) {
        if (amount == 0) {
            ans ++;
            return;
        }        
        for (int i = idx; i < coins.size(); ++ i) {
            if (amount >= coins[i]) {
                // choose coins[i] and solve a smaller problem recursively
                dfs(amount - coins[i], coins, i);
            }
        }
    }
};

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        dfs(amount, coins, 0);
        return ans;
    }
private:
    int ans = 0;
    void dfs(int amount, vector<int>& coins, int idx) {
        if (amount == 0) {
            ans ++;
            return;
        }        
        for (int i = idx; i < coins.size(); ++ i) {
            if (amount >= coins[i]) {
                // choose coins[i] and solve a smaller problem recursively
                dfs(amount - coins[i], coins, i);
            }
        }
    }
};

We recursively solve a smaller problem and when the amount is reduced to zero, we can increment the answer. The problem with above C++ DPS recursive implementation is that the intermediate smaller problems are computed again and again, which leads to exponential complexity O(N^N) where N is the number of the coin values.

Solving the Unlimited Knapsack Combination via Dynamic Programming

dynamic-programming-interview-questions

We can use the F(N) to represent the number of combinations for amount N, then following DP equation applies:

1
2

f[0] = 1; // for zero amount, only 1 combination which is 0.
f[n] = sum(F[N-c]); // c - the coin values.

f[0] = 1; // for zero amount, only 1 combination which is 0.
f[n] = sum(F[N-c]); // c - the coin values.

As such, the intermediate results are remembered in the F array, and the complexity is O(NM) where N is the number of different items e.g. coins, and the M is the amount e.g. the total capacity for the knapsack. The below C++ uses O(M) additional space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> f(amount + 1, 0);
        f[0] = 1;
        for (const auto &c: coins) {
            for (int i = 1; i <= amount; ++ i) {
                if (i >= c) {
                    f[i] += f[i - c];
                }
            }
        }
        return f[amount];
    }
};

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> f(amount + 1, 0);
        f[0] = 1;
        for (const auto &c: coins) {
            for (int i = 1; i <= amount; ++ i) {
                if (i >= c) {
                    f[i] += f[i - c];
                }
            }
        }
        return f[amount];
    }
};

See also: Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem

Knapsack Problems

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —