2. A greedy algorithm is one in which we always choose the \"biggest\" move, und

Question

2. A greedy algorithm is one in which we always choose the "biggest" move, under some definition of the size of each move. When we refer to The Greedy Algorithm, we mean the original and still most used one how to make change. When we need to get a certain amount of money, we generally begin by taking the largest denomination less than or equal to the amount we want, then the largest for the amount remaining, etc. For example, if we need to get 17e, we begin by taking a dime, then a nickel, and then two cents. There are many cases where greedy algorithms give us the most efficient methods. This is true for making change, where the algorithm minimizes the number of coins and bills to be used. his is only because of our particular denominations. If we had coins worth 1, 8, and 10 cents, then the Greedy Algorithm would not yield the minimum number of coins for getting 17c.] If we are given only pennies, nickels, and dimes, show that the Greedy Algorithm allows us to get any amount of money using the minimum number of coins.

Explanation / Answer

1)
First one we can directly prove.
given equation is
2a+5b=0(mod7)

which means equivalence relationship...===> 0=2a+5b(mod7)

consider if a=1, b=1 then 7(mod 7) =0 ehich means correct..
since R is in equivalence relation since it is equivalence , reflexive and transitive.

2)
as per situation given in question it doesnot yield our required minimum solution. so let us do using greedy approach..using some recursive calls

If the cents does not match we have several options. so now what we required is minimum cents and also number of coions that make change original
cents minus a penny or a nickel plus the number of coins needed to make change for the original amount minus eight cents, or a dime plus the number
of coins needed to make change for the original amount minus ten cents, and so on. so calculations equations are here
Number of coins = minimum { 1+ NumberOfCoins(GivenCents -1) // 1+ NumberOfCoins(GivenCents -8) // 1+ NumberOfCoins(GivenCents -10) }
In program we are checking our base case; that is, we are trying to make change in the exact amount of one of our coins. If we do not have a coin equal
to the amount of change, we make recursive calls for each different coin value less than the amount of change we are trying to make.
The recursive call also reduces the total amount of change we need to make by the value of the coin selected.

So number would be 1 dime 1 cents
1 nickel 8 cents
1 penny 10 cents which means minimum coins required are 3.

sample code to show tht above algorithm:

def recursiveCall(listOfCoinsValues,val_change,knownResults):
minCoins = val_change
if val_change in listOfCoinsValues:
knownResults[val_change] = 1
return 1
elif knownResults[val_change] > 0:
return knownResults[val_change]
else:
for i in [c for c in listOfCoinsValues if c <= val_change]:
numCoins = 1 + recursiveCall(listOfCoinsValues, val_change-i,
knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[val_change] = minCoins
return minCoins

print(recursiveCall([1,8,10],17,[0]*18))

output will be 3

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.