Hello! Today we will discuss one of the frequently asked questions in C++ coding tests, which is ‘Finding the Minimum Number of Coins.’ This problem is a basic algorithm problem that determines the minimum number of coins needed to make a given amount. We will analyze this problem step by step and solve it through implementation.<\/p>\n
Given the types of coins and a target amount, find out the minimum number of coins required to make that amount. Each coin is assumed to be available in infinite supply.<\/p>\n
N<\/code> (1 \u2264 N \u2264 100).<\/li>\n- The second line contains
N<\/code> integers representing the value of each coin.<\/li>\n- The third line contains the target amount
M<\/code> (1 \u2264 M \u2264 10,000).<\/li>\n<\/ul>\nOutput Format<\/h3>\n\n- Output the minimum number of coins needed to make the target amount. If it is not possible to make the target amount, output
-1<\/code>.<\/li>\n<\/ul>\nExample<\/h2>\n\nExample Input:\n3\n1 3 4\n6\n\nExample Output:\n2\n<\/pre>\nIn the above example, there are 3 types of coins with values of 1, 3, and 4. To make the target amount of 6, using the coins 3 and 3 will result in a total of 2 coins.<\/p>\n
Approach to Solve the Problem<\/h2>\n
This problem can be solved using Dynamic Programming or Greedy Algorithm. However, when there are multiple types of coins, using Dynamic Programming provides a more general solution. Below is the approach to solving the problem using Dynamic Programming.<\/p>\n
Basic Concept of Dynamic Programming<\/h3>\n
Dynamic Programming (DP) is a method of solving large problems by dividing them into smaller ones. In this problem, we can reduce redundant calculations while finding the minimum number of coins required to make each amount to reach the target amount. We will use a DP array to store the minimum number of coins needed for each amount.<\/p>\n
Definition of DP Array<\/h3>\n
We define dp[i]<\/code> as the minimum number of coins needed to make the target amount i<\/code>. We set the initial value dp[0] = 0<\/code> and initialize the other amounts to INT_MAX<\/code> (infinity).<\/p>\nSolution<\/h2>\n
Now, let’s implement this based on the theory. The code is as follows:<\/p>\n
\n#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <climits>\nusing namespace std;\n\nint main() {\n int N, M;\n cin >> N; \/\/ Input the number of coin types\n vector coins(N);\n for (int i = 0; i < N; ++i) {\n cin >> coins[i]; \/\/ Input the value of each coin\n }\n cin >> M; \/\/ Input the target amount\n\n vector dp(M + 1, INT_MAX); \/\/ Initialize DP array\n dp[0] = 0; \/\/ The number of coins needed to make 0 amount is 0\n\n \/\/ Fill the DP array\n for (int i = 1; i <= M; ++i) {\n for (int j = 0; j < N; ++j) {\n if (coins[j] <= i) {\n dp[i] = min(dp[i], dp[i - coins[j]] + 1);\n }\n }\n }\n\n \/\/ Output the result\n if (dp[M] == INT_MAX) {\n cout << -1 << endl; \/\/ If it cannot be made\n } else {\n cout << dp[M] << endl; \/\/ Output the minimum number of coins\n }\n\n return 0;\n}\n<\/int><\/int><\/code><\/pre>\nCode Explanation<\/h3>\n\n- First, include the necessary libraries and input the number of coin types and the target amount.<\/li>\n
- Define a vector
coins<\/code> to store the values of the coins and an array dp<\/code> to store the number of coins.<\/li>\n- Use a nested loop to fill the
dp<\/code> array. The outer loop iterates over the target amount, and the inner loop iterates over the types of coins to calculate the minimum number of coins.<\/li>\n- In the end, if the value of
dp[M]<\/code> is INT_MAX<\/code>, it means the amount M cannot be made, so output -1<\/code>. Otherwise, output the minimum number of coins.<\/li>\n<\/ul>\nComplexity Analysis<\/h2>\n