All Questions
16 questions
1
vote
1
answer
89
views
Why two seemingly similar implementations of the same DP algorithm differ?
I'm implementing a dynamic programming (DP) solution to an "unbounded knapsack"-family problem.
To be more precise, the problem is to find all possible change for the given amount having a ...
- 73
0
votes
2
answers
84
views
Dynamic programming solution inappropriate for change-making problem?
I'm curious why my approach to the change-making problem isn't succeeding. The logic makes sense to me, so I'm not sure where the failure is.
def count_change(denoms, denoms_length, amount):
"...
- 1,248
0
votes
3
answers
235
views
How to find subsets from a set that product equals the target?
Let us say we have a list and target of:
list: [1,2,3,4,5] and target: 20
and we want to find total combinations to reach this, with multiplication, which is:
[1,4,5], [4,5], [2,5,2], [1,2,2,5]
I did ...
0
votes
1
answer
295
views
Leetcode 322: Coin change recursive approach gives wrong answer
I'm trying to solve the famous coin change problem using the naive recursive solution (I'll use this as a blueprint before adding memoization or tabulation).
You are given an integer array coins ...
- 1,705
1
vote
1
answer
771
views
Coin change problem: top down approach seems to not be polynomial
The coin change problem (see leet code page here) gives us some coins of certain denominations in an array, c. Then, given a target amount, t, we want to find the minimum coins required to get that ...
- 2,691
0
votes
2
answers
200
views
Implementing minimal coin amount for change with memoization?
I'm practicing the concepts of Dynamic Programming (recursion is not my strong suit). I was wondering how my piece of code may be improved so that I can avoid a stack overflow.
Anything helps, thanks!
...
- 308
1
vote
3
answers
1k
views
Coin Change Problem with Dynamic Programming
This is my code regarding the Coin Change Problem for print the total number of ways for a set of coins and the target amount
def coin_change(coins,amount):
table=[0 for k in range(amount+1)]
...
- 13
2
votes
1
answer
1k
views
Dynamic programming, minimum number of coins
I have been studying algorithms and data structures off https://runestone.academy/runestone/static/pythonds/index.html, and I got to the part about dynamic programming and the classic minimum number ...
- 397
0
votes
1
answer
89
views
Why is a variable in my coin-changing (DP) function changing?
The task is to write a function to make change for an amount using a given denomination of coins (coins = [200, 100, 50, 20, 10, 5, 2, 1]), given the coins in 'pocket' e.g a pocket of [1,0,1,0,5,0,3,0]...
0
votes
2
answers
741
views
Python Coin Change Dynamic Programming
I am currently trying to implement dynamic programming in Python, but I don't know how to setup the backtracking portion so that it does not repeat permutations.
For example, an input would be (6, [1,...
4
votes
1
answer
2k
views
Dynamic change-making algorithm that returns actual list of coins used
I'm trying to adjust the code from the wikipedia:
https://en.wikipedia.org/wiki/Change-making_problem#Implementation
To also output the list of coins used, not only the number of coins used. That is,...
- 1,260
0
votes
0
answers
311
views
coin change function using unbounded knapsack python
I'm trying to write a coin change function. The idea is that I have unlimited denominations and whatever value and trying to see what kind of change I can get. I thought this could be done like an ...
- 31
2
votes
1
answer
685
views
Memoization: Making change with coins
I am working on the classic making change with coins problem with Python. This is my implementation.
def memo(fn):
def helper(*args): # here, * indicate the fn take arbitrary number of argumetns
...
- 337
18
votes
4
answers
21k
views
Understanding change-making algorithm
I was looking for a good solution to the Change-making problem and I found this code(Python):
target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
for i in range(...
- 537
6
votes
3
answers
17k
views
Recursive change-making algorithm
Given a target amount and a list of coin denominations, my code is supposed to find the fewest coins needed to reach the target amount.
Examples:
C(78, [1, 5, 10, 25, 50]) = 6
we can make 78 from ...
- 1,811