Suppose that we want to make change for n cents using the least number of coins....

Suppose that we want to make change for n cents using the least number of coins. The coins are of denominations c 0 , c 1 , . . . , c k for some integers c > 1, and k ≥ 1. (a) Design a greedy algorithm to solve this problem. (b) Prove that your algorithm finds an optimal solution by showing the greedy-choice property and optimal substructure for it. Clearly state each property and then prove them.

Expert Solution

Answer a). Always give the highest denomination coin that you can without going over. Then, repeat this process until the amount of remaining change drops to 00.

Answer b)

Let the coin denominations be {1, 3, 4}{1,3,4}, and the value to make change for be 66. The greedy solution would result in the collection of coins {1, 1, 4}{1,1,4} but the optimal solution would be {3, 3}{3,3}.

note: plzzz don't give dislike.....plzzz comment if you have any problem i will try to solve your problem.....plzzz give thumbs up i am in need....

venereology answered 6 months ago

Prove that it is possible to make up any postage of n-cents using only 5-cent and...

Prove that it is possible to make up any postage of n-cents using only 5-cent and 9-cent stamps for n ≥ 35.

(i) T(n) denote the number of distinct ways that a postage of n cents, where n...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n ≥ 4 and n is even, can be made by 4-cent and 6-cent stamps. Find a recurrence relation T(n). NOTE [4,6] is the same as [6,4] so T(10) = 1 so T(n) is NOT T(n-4)+T(n-6) (ii) Now assume we have 10-cent stamps in addition to the previous 2 kinds. Find a recurrence relation, S(n), for the number of distinct ways that a postage of...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n ≥ 4 and n is even, can be made by 4-cent and 6-cent stamps. Give a recursive algorithm (written in Python) to compute T(n) for n ≥ 4 and n is even. Brieﬂy explain why the algorithm is correct but no formal proof is required. NOTE [4,6] is the same as [6,4] so T(10) = 1. (ii) Now assume we have 10-cent stamps in...

Create a program/function using PYTHON that takes cents and returns to the customer how MANY coins...

Create a program/function using PYTHON that takes cents and returns to the customer how MANY coins it takes to make the change... Ex. if the change owed is 50 cents then return a 2 (for two quarters) if the change owed is 10 cents then return a 1 (for one dime) AGAIN please write this in java and please provide EXPLANATION of answer

using math lab, Write a code to compute the change in dollars (no cents) to be...

using math lab, Write a code to compute the change in dollars (no cents) to be given back to a restaurant patron who pays the bill in cash. That is, find and enumerate the various combinations (of common currency notes only) that can amount to the change due.

A. How many ways are there to make 35 cents change in 1952 pennies, 1959 pennies...

A. How many ways are there to make 35 cents change in 1952 pennies, 1959 pennies and 1964 nickels? B. In 1952 pennies, 1959 pennies, 1964 nickels and 1971 quarters?

Suppose a coin is tossed 100 times and the number of heads are recorded. We want...

Suppose a coin is tossed 100 times and the number of heads are recorded. We want to test whether the coin is fair. Again, a coin is called fair if there is a fifty-fifty chance that the outcome is a head or a tail. We reject the null hypothesis if the number of heads is larger than 55 or smaller than 45. Write your H_0 and H_A in terms of the probability of heads, say p. Find the Type I...

Suppose there are unlimited number of Red, Green, and Blue balls, You want to select n...

Suppose there are unlimited number of Red, Green, and Blue balls, You want to select n balls and the orders matter. The selected balls must meet the following rule: Two adjacent balls must not be both Red or both Blue. How many options do you have when n is 4?

Suppose you have N items with values xi from which we want to sample n items...

Suppose you have N items with values xi from which we want to sample n items with replacement. Each item has its own probability pi of being selected across all times we pick items. What's the estimated variance of the Horvitz-Thompson estimator of T? Let T = > 1, 1=1

Suppose you have N items with values xi from which we want to sample n items...

Suppose you have N items with values xi from which we want to sample n items with replacement. Each item has its own probability pi of being selected across all times we pick items. What's the bias for the following estimator of T: Let T = > 1, 1=1

Question

Suppose that we want to make change for n cents using the least number of coins....

Solutions

Expert Solution

Related Solutions

Prove that it is possible to make up any postage of n-cents using only 5-cent and...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n...

Create a program/function using PYTHON that takes cents and returns to the customer how MANY coins...

using math lab, Write a code to compute the change in dollars (no cents) to be...

A. How many ways are there to make 35 cents change in 1952 pennies, 1959 pennies...

Suppose a coin is tossed 100 times and the number of heads are recorded. We want...

Suppose there are unlimited number of Red, Green, and Blue balls, You want to select n...

Suppose you have N items with values xi from which we want to sample n items...

Suppose you have N items with values xi from which we want to sample n items...