All Questions
Tagged with coin-change algorithms
11 questions
1
vote
1
answer
94
views
Coin exchange, find different triples of values
Suppose i have 3 coins: A, B, C. Each one of them have different value: a, b, c. And if want to exchange coins A for coins B, i need to be able to give exactly a units of currency A and get exactly b ...
- 11
0
votes
1
answer
919
views
What is the best way to solve the coin change problem using dynamic programming?
I have found two ways of applying dynamic programming to the coin change problem of finding the minimum number of coins from a given set of denominations to make a given sum. I wanted to know if one ...
- 111
6
votes
2
answers
2k
views
Why does the order of the nested loops matter when solving the Coin Change problem?
The Coin Change problem is stated as:
Given an integer array coins[ ] of size N representing different
denominations of currency and an integer sum, find the number of ways
you can make sum by using ...
- 171
2
votes
3
answers
530
views
Algorithm for fewest number of moves with artificial minimum
I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum.
To summarize, I built an undirected graph with edges ...
- 103
1
vote
1
answer
2k
views
What Are the Ideas Behind Variations of the Coin Change Problem?
Problem: given a set of n coins of unique face values, and a value
change, find number of ways of making change for ...
- 303
1
vote
1
answer
350
views
"Ways to make change for a dollar": How to optimize with constraints
I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for ...
- 113
0
votes
0
answers
286
views
Implementing supplies in Coin change problem
I started an algorithm course in C two months ago, for the last weeks I've been trying to solve this problem , i ran out of time but I cannot find an acceptable solution. Basically It's a coin change ...
- 1
9
votes
1
answer
6k
views
Analyzing time complexity for change making algorithm (Brute force)
I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so:
Since the tree can have a maximum height of 'n' and at every ...
- 193
2
votes
2
answers
3k
views
What are applications of Coin Change problem?
I've read so many about the Coin Change problem, debates about wheather it is solvable using Greedy, Dynamic Programming and so on.
Nevertheless I cannot find an application of this problem.
What ...
- 874
2
votes
3
answers
924
views
Coin Change Problem(Greedy Algorithm)
In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm?
Example- $(1,3,4)$ are denominations of coin.
If I want to pay ...
- 21
3
votes
1
answer
3k
views
A variant of coin change problem
Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in ...
- 339