How to approach greedy in problem set 1? [closed]

Question

I do not have a clear idea of how greedy can be solved.

I do not understand this currency or what the question asks.

Answer 1

You are given a value of dollars and cents. You must calculate the least number of coins that can be used to make that value. The coins available are worth 25 cents (quarter), 10 cents (dime), 5 cents (nickel), and 1 cent (penny).

Let's say you are asked for 1.32

1.32 is 132 cents. So how many coins would you need? To get the least number of coins, you should start with the coin with the highest value (the quarter or 25 cent coin).

So, 132 cents / 25 cents = 5 so you have 5 quarters (worth 25*5 = 125 cents).

That means you still need coins for 132 - 125 cents which is 7 cents.

Next, try your next coin value, which is 10 cents.

7 cents / 10 cents = 0 (so that means you can't use any dimes)

Next, try nickels

7 cents / 5 cents = 1 (so one nickel), leaving 7-5 = 2 cents (2 pennies)

So, total coins is 5 + 0 + 1 + 2 = 8

Your answer is 8.

I hope that is understandable.

Answer 2

CS50 provides a variety of resources to help their students including walkthroughs for the each of the problem sets. The walkthroughs help get you started and show how you should be thinking about solving the problems presented. I've listed the link to the CS50 walkthrough on greedy.c

https://www.youtube.com/watch?v=9dZzyl7dCuw

Answer 3

Imagine you have unlimited number of coins.
I ask you to give me 1 dollar.
You can give me 100 pennies (1 cent coin).
Or 20 nickels (5 cent coin).
Or 10 dimes (10 cent coin).
Or 4 quarter (25 cent coin).
Or some combination of this coins, say 1 quarter, 6 dimes, 2 nickels and 5 pennies.

Let's say than fewer coins you give me - the better.

So your task is to write a program that will accept a number (of cents you have to give to me) and tell you the minimum number of coins that you can give to me.