in coin changing problem, show that the greedy strategy fails for the denominations 25, 20, 10, 5, and 1 cents. (hint: prove that we cannot construct the solution by making decisions to choose each item to add to the solution optimally, and never reversing decisions already made

Question

19-12-2022
Mathematics

Answered

in coin changing problem, show that the greedy strategy fails for the denominations 25, 20, 10, 5, and 1 cents. (hint: prove that we cannot construct the solution by making decisions to choose each item to add to the solution optimally, and never reversing decisions already made

Answer :

Other Questions

1 1 3 What is the solution of c-3c(c-3)? O c = 0 and c = 3 O all real numbers all real numbers, except c ¹0 and c¹3 Ono solution

The vector (2, 6) describes the translation of M(3, 2w) to M'(4x - 2, 7) and N(5y - 8,9) to N'(0,3/2z). What is the sum of w, x, y, and z?

Hi, I can’t solve all of these questions, could someone please help me out? 1) The manager of a clothing company is analyzing its costs, revenues, and profits t

Find the term that must be added to the equation 2 - 8x = 9 to make it into a perfect square. A. 64 B.-9 C. 16 D. 32

Use the two-way table to match each description with its value. Use each value, rounded to the nearest percent, only once.

Evaluate the expression for x= 4 and y =2

It rains, and the wind is never weary; My thoughts still cling to the moldering Past, But the hopes of youth fall thick in the blast, And the days are dark and

Write the equation for the line shown in the picture

For which value(s) of a in the interval 0° ≤ x ≤ 180° is sin (3x) = 1? O 90° O 0° and 120° O 300 and 150⁰ O 600 and 180° none of the above

smecloudbird18 smecloudbird18 · Answer 1 · 2022-12-23T07:19:06-05:00

In coin changing problem, the greedy strategy fails for the denominations 25, 20, 10, 5, and 1 cents.

The greedy algorithm for the coin change problem (pay a certain amount with the fewest number of coins feasible) is effective. It always chooses the coin with the largest denomination that does not exceed the remaining sum, and it consistently determines the right answer for certain coin sets.

But for certain set of denominations, it fails. For example take a sum of 44 cents then by greedy algorithm, first taking the highest denominations one 25 cent is taken and now 19 is remaining. So now one 10 cent is taken, and 9 is remaining. Now, one 5 cent is taken and four 1 cent is taken. So total we get 7 coins.

Now let us deviate from greedy algorithm and take two 20 cents, now 4 is remaining. So now four 1 cent is taken, this sums up only 6 coins. So this is a much optimal solution than the one obtained by greedy algorithm.

To know more on greedy algorithm

https://brainly.com/question/13197481

#SPJ4