Use Dynamic Programming to find the minimum number coins you can change for the given amount of money (W=7) using given coins(1,3,4,5).
Question
Use Dynamic Programming to find the minimum number coins you can change for the given amount of money (W=7) using given coins(1,3,4,5).
Solution
Sure, here is a step-by-step solution using Dynamic Programming to find the minimum number of coins you can change for the given amount of money (W=7) using given coins(1,3,4,5).
Step 1: Initialize an array dp of size W+1 to store the minimum number of coins needed to make change for all values from 0 to W. Set dp[0] = 0 because no coins are needed to make change for 0.
Step 2: For each coin value, the coin cannot contribute to the solution of smaller amounts than its own value. So, start the iteration from the coin value till the amount W.
Step 3: For each amount i from 1 to W, compute the minimum number of coins needed. The minimum number of coins needed to make change for amount i is 1 (using coin of value i) plus the minimum number of coins needed to make change for amount (i - coin value).
Step 4: Store the minimum number of coins needed to make change for amount i in dp[i].
Step 5: Continue the process until we have computed dp[W], which will hold the result.
Here is the Python code for the above steps:
def minCoins(coins, W):
dp = [0] + [float('inf')] * W
for i in range(1, W+1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i-coin] + 1)
return dp[W]
coins = [1,3,4,5]
W = 7
print(minCoins(coins, W))
This code will output 2, which is the minimum number of coins needed to make change for amount 7 using coins of values 1,3,4,5.
Similar Questions
Use Dynamic Programming to find the total number of ways you can change the given amount of money (W=5) using given coins(2,3,5).
A sum of money is to be shared in the ratio 3:5:7. If the smallest share is $9, how much money is shared?
I have 45 coins in my pocket. They are all either nickels or quarters. Thevalue of the coins is $5.65. How many of each coin do I have?
Sue has 100 dimes and quarters. If the total value of the coins is $21.40, how many quarters does she have? Write and solve the system of equations.
Find the sum of first all integers between 100 and 1000 which are divisible by 7.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.