Greedy algorithm to find minimum number of coins
The problem at hand involves finding the minimum number of coins needed to make up a given value using a greedy algorithm approach. In other words, we want to determine the combination of coins that adds up to the desired value while minimizing the total number of coins used. This problem has applications in various domains such as currency exchange, vending machines, and optimization algorithms.
Problem Statement and Description
Given a set of coin denominations (e.g., 1 cent, 3 cents, 4 cents, 6 cents), we are asked to find the minimum number of coins required to make a given value (e.g., 23 cents, 38 cents, 7 cents). We need to identify the combination of coins that adds up to the desired value while using the least number of coins possible.
Example
Let's take the coin denominations as [1, 3, 4, 6] and work through a few examples.
-
For the value 23: The greedy algorithm will start by picking the largest coin that is less than or equal to the remaining value. It repeatedly does this until the total value matches the desired value. The process can be understood as follows:
- Start with value = 23, choose coin 6 (23 - 6 = 17)
- Choose coin 6 again (17 - 6 = 11)
- Choose coin 6 again (11 - 6 = 5)
- Choose coin 4 (5 - 4 = 1)
- Choose coin 1 (1 - 1 = 0) Thus, the minimum coins are [6, 6, 6, 4, 1].
-
For the value 38:
- Choose coin 6 repeatedly (38 - 6 = 32)
- Choose coin 6 repeatedly (32 - 6 = 26)
- Choose coin 6 repeatedly (26 - 6 = 20)
- Choose coin 6 repeatedly (20 - 6 = 14)
- Choose coin 6 repeatedly (14 - 6 = 8)
- Choose coin 6 repeatedly (8 - 6 = 2)
- Choose coin 1 (2 - 1 = 1)
- Choose coin 1 (1 - 1 = 0) The minimum coins are [6, 6, 6, 6, 6, 6, 1, 1].
-
For the value 7:
- Choose coin 6 (7 - 6 = 1)
- Choose coin 1 (1 - 1 = 0) The minimum coins are [6, 1].
Idea to Solve the Problem
The greedy algorithm works by repeatedly selecting the largest coin denomination that can be used without exceeding the remaining value. This approach aims to use the largest coins first to minimize the total number of coins used.
Pseudocode
- Sort the coin denominations in descending order.
- Initialize a vector (or list) to keep track of the selected coins.
- Initialize variables:
sum
to keep track of the current sum of coin values,i
to point to the current coin denomination being considered, andc
to store the value of the current coin. - While
i
is greater than or equal to 0 andsum
is less than the desired value:- Set
c
to the value of the coin at indexi
. - While adding
c
tosum
doesn't exceed the desired value, addc
to the selected coins list and updatesum
. - Decrement
i
.
- Set
- If
sum
is equal to the desired value, print the selected coins. Otherwise, print a message indicating that full change is not possible.
Code Solution
-
1) Coin change using greedy algorithm in java
2) Coin change using greedy algorithm in c++
3) Coin change using greedy algorithm in c#
4) Coin change using greedy algorithm in php
5) Coin change using greedy algorithm in python
6) Coin change using greedy algorithm in ruby
7) Coin change using greedy algorithm in scala
8) Coin change using greedy algorithm in swift
9) Coin change using greedy algorithm in golang
10) Coin change using greedy algorithm in kotlin
11) Coin change using greedy algorithm in vb.net
12) Coin change using greedy algorithm in node js
Time Complexity
The time complexity of this greedy algorithm primarily depends on the sorting step, which takes O(n log n), where n is the number of coin denominations. The while loop that follows iterates through the coin denominations and adds coins until the desired value is reached, which takes O(n). Therefore, the overall time complexity of the algorithm
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment