All Questions
Tagged with coin-change dynamic-programming
15 questions
1
vote
1
answer
70
views
Minimum coins to make change when real numbers are allowed
There is the classical version of the minimum coins to make change problem where the change and the set of coins available are all integers. Given an infinite amount of each type of coin, we're asked ...
- 375
0
votes
1
answer
921
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
1
vote
1
answer
79
views
Unable to understand how the while loop extracts the least number of coins with given sum
I was reading this classical Coin Problem (7.1): Given a set
of coin values coins = {c1, c2,..., ck} and a target sum of money n, our task is to
form the sum n using as few coins as possible.
I fully ...
1
vote
1
answer
122
views
Can the algorithm be optimized?
I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
- 131
2
votes
1
answer
3k
views
Min-coin change problem with limited coins
I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
- 123
1
vote
1
answer
1k
views
dynamic pseudo-code for simplified coin changing algorithm
As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible ...
- 205
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
3
votes
2
answers
3k
views
DP recurrence relations: Coin change vs Knapsack
Take:
KP recurrence relation
$ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0
CCP recurrence relation
$ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0
I don't ...
- 33
3
votes
3
answers
6k
views
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.
This question is a simplification of ...
- 245
1
vote
2
answers
2k
views
Printing actual solutions for the coin exchange problem
As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight ...
2
votes
1
answer
1k
views
Dynamic Programming for a variant of the coin exchange problem
I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem:
Given a value N, if we want to make change for N cents, and we have ...
5
votes
2
answers
1k
views
Can counting problems have optimal substructure?
I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties:
optimal substructure
overlapping subproblems
I stumbled upon an article which ...
- 220
3
votes
1
answer
7k
views
Recurrence relation of the coin change problem
I'm trying to wrap my head around the coin change problem, where you try to find the total number of ways $N$ cents can be exchanged using $M$ coins $\{C_1, C_2, ..., C_m\}$.
The recurrence relation ...
- 214
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