1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Ainat [17]
3 years ago
14

Suppose we need to make change for n cents, and we want to use the least number of coins of denominations 1, 10, and 25 cents. C

onsider the following greedy strategy: suppose the amount left to change is m. Take the largest coin that is no more than m, subtract this coin’s value from m, and repeat. Prove that this algorithm is optimal, or give a counterexample if it is not.
Mathematics
1 answer:
frutty [35]3 years ago
8 0

Answer:

Explained

Step-by-step explanation:

This algorithm does not always give the optimal solution.  There is an alternate method as well.

Consider we have to make change for 30 cents, using the least number of coins of denominations 1,10 and 25 cents.According to the given strategy, we first take a 25 cents coin and subtract it from 30 cents. Now, we have to make 5 cents which we can make only from 5 one-cent coins. So, the total number of coins required is 6 according to the given greedy strategy.

But we can simply use 3 ten-cent coins to make change of 30 cents. So, this example proves that the given strategy is not an optimal one.

You might be interested in
You have two ways to drive home from school: Route A is usually quicker; Route B is
Brilliant_brown [7]

Answer:

0.12 = 12%

Step-by-step explanation:

To find this probability, we need to multiply the probability of getting route B, and the probability of getting home by 4 P.M if we choose route B.

If the probability of choosing route A is 60%, we have that the probability of choosing route B is 100% - 60% = 40%

Then, we have that the probability of getting home by 4 P.M. when choosing route B is 30%, so the final probability is:

P = 40% * 30% = 0.4 * 0.3 = 0.12 = 12%

4 0
3 years ago
What is 265 times 14.? Explain what you did.
AysviL [449]

Answer:

3710

Step-by-step explanation:

265 * 14    

multiply 4 by 5, then 4 by 6, then 4 by 2 which would look like this 860

then you multiply 1 by 5, then 1 by 6, then 1 by 2 which should loo like 2650

it looks like that because for every digit you multiply by except the first you add a zero in front of it. then you add those two up which adds up to 3710 you're welcome. :}

5 0
3 years ago
Read 2 more answers
Two fair dice are thrown. Let X be a random variable giving the score on the rst die and Y be a random variable giving the large
defon

Answer:

idk

idkidk

Step-by-step explanation:

5 0
3 years ago
Someone tell me the anwser and i need to show my work too
Zinaida [17]
First you need to find how much 20% of $18.50 is. To do this, you need to multiply 18.50 by 20% which in decimal form is 0.2
$18.50x0.2=$3.70
Now you need to subtract $3.70 from $18.50
$18.50-$3.70=$14.80
Now that you have the new price, you need to find 6.75% of it to get the sales tax, so you multiply $14.80 by 6.75%, which is 0.0675 as a decimal.
$14.80x0.0675=$0.999 or $1 
Now you add the sales tax to $14.80
$14.80+$1=$15.80 or $14.80+$0.999=$15.799
6 0
3 years ago
Read 2 more answers
What is the factor of 16
insens350 [35]
1x16
2x8
is the answer
3 0
3 years ago
Read 2 more answers
Other questions:
  • A concert manager counted 550 ticket receipts the day after a concert. The price for a student ticket was $12.50, and the price
    8·1 answer
  • the hypotenuse and a side of a right angled triangle are 13cm and5cm respectively. fined the length of the third side​
    14·2 answers
  • Determine the value(s) for which the rational expression f(x)=(?11x+1)/(?30x^2?25x+5) is undefined. If there's more than one val
    11·1 answer
  • Find the distance between points (-1.4) and (1,-1).
    13·1 answer
  • What is the equivalent decimal of -1\5 and -2\9
    13·1 answer
  • Which fractions has the least common denominator of 24 ​
    5·1 answer
  • Which equation can be used to prove 1 + tan?(x) = sec2(x)?
    9·1 answer
  • For a unit circle determine the ordered pairs that are associated with any angle that has a reference to 30 degrees?
    10·1 answer
  • What is the area of this figure?
    9·1 answer
  • 86 1/10 is greater than, lesser than, or equal to 0.62
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!