Knowee
Questions
Features
Study Tools

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).

🧐 Not the exact question you are looking for?Go ask a question

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.

This problem has been solved

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?

I am a coin. If you take 30 coins like me, you can make more than Rs. 5. If you take 20 coins like me, you will make less than Rs. 5. What is my value?

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.

1/1

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.