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

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

You may assume that you have an infinite number of each kind of coin.

This is one variant of the classic knapsack problem where you can use unlimited items of a kind. The target is to find the shortest solution to pack the least number of items so that the entire bag has been filled.

Breadth First Search Algorithm for Unlimited Knapsack Problem

The shortest, smallest or fastest keywords hint that we can solve the problem using the Breadth First Search algorithm. We start by push the root node that is the amount. Then, for each coin values (or item weight), we push the remaining value/weight to the queue. At any time, if the remaining balance equals to the item value, we simply return its depth as it will the shortest path from the root.

The following C++ implements the BFS algorithm and we use a hash set to remember the nodes that we have already expanded so that they will not be computed again and again.

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

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        queue<pair<int, int>> Q;
        if (amount == 0) return 0;
        Q.push({amount, 0});
        unordered_set<int> v;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            for (const auto &n: coins) {
                if (p.first > n && (v.count(p.first - n) == 0)) {
                    Q.push({p.first - n, p.second + 1});
                    v.insert(p.first - n);  // avoid memory limit
                } else if (p.first == n) {
                    return p.second + 1;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        queue<pair<int, int>> Q;
        if (amount == 0) return 0;
        Q.push({amount, 0});
        unordered_set<int> v;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            for (const auto &n: coins) {
                if (p.first > n && (v.count(p.first - n) == 0)) {
                    Q.push({p.first - n, p.second + 1});
                    v.insert(p.first - n);  // avoid memory limit
                } else if (p.first == n) {
                    return p.second + 1;
                }
            }
        }
        return -1;
    }
};

The space complexity will be O(amount) and the time complexity will be O(amount*N) where N is the number of different items (coins).

Dynamic Programming Algorithm to Solve the Unlimited Knapsack Problem

dynamic-programming-interview-questions

If we observe the above BFS, we might notice that the intermediate answers can be cached and re-used. If we use F(n) to denote the shortest items that we can put to fit the weight n, we can easily obtain the following DP equation:

F(i) = min(F(i), F[i – n] + 1) where n is the weight/value for each item, when i is bigger than n.

Thus, the following C++ implements a Dynamic Programming algorithm where the time complexity is O(amount * N) i.e. the N is the number of items. The initial value will be F(0) = 0 and the space complexity is O(amount).

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

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i <= amount; ++ i) {
            for (const auto &n: coins) {
                if (i >= n && (f[i - n] != INT_MAX)) {
                    f[i] = min(f[i], f[i - n] + 1);
                }
            }
        }
        return f[amount] == INT_MAX ? -1 : f[amount];
    }
};

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i <= amount; ++ i) {
            for (const auto &n: coins) {
                if (i >= n && (f[i - n] != INT_MAX)) {
                    f[i] = min(f[i], f[i - n] + 1);
                }
            }
        }
        return f[amount] == INT_MAX ? -1 : f[amount];
    }
};

If you want to find out all possible combination, you can use the backtracking algorithm, as detailed in solving another similar puzzle.

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

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) —