Give an instance of the making-change problem

Assignment Help Computer Engineering

Reference no: EM132139791

Question :

Suppose that the coins of the fictional country of Combinatoria come in the de- nominations, d1, d2, . . . , dk, where d1 = 1 and the other di values form a set of distinct integers greater than 1. Given an integer, n > 0, the problem of making change is to find the fewest number of Combinatorian coins whose values sum to n.

(a) Give an instance of the making-change problem for which it is suboptimal to use the standard greedy algorithm, which repeatedly chooses a highest-valued coin whose value is at most n until the sum of chosen coins equals n. (writeup only)

(b) Implement the algorithm for the coin changing problem. Take as input a file with a set of denominations. Interactively ask the user for the amount he wants to make change for and print the number of coins and the actual change.

Reference no: EM132139791

Questions Cloud

Fifty-seven percent of employees make judgements : Fifty-seven percent of employees make judgements about their co-workers based on the cleanliness of their desk.

Test scores on the law school admission test : What is the probability that the mean of 12 randomly selected scores is less than 161?

For which values of n does insertion sort beat merge sort : For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64nlgn steps.

Calculate the project initial investment costs : Calculate the project's initial investment costs, annual incremental operating cash flows, and terminal cash flows. What are project's NPV and IRR

Give an instance of the making-change problem : Give an instance of the making-change problem for which it is suboptimal to use the standard greedy algorithm.

What is the probability that at least : If you select 31 customers, what is the probability that at least 20 of them have looked at their score in the past six months?

Discuss about the computer security consulting services : Determine whether you would employ a hierarchical, a flat, or a matrix organizational structure, and explain why.

Show your structure before and after the deletion : A B+ tree in which the deletion of the value 42 leads to a redistribution. Show your structure before and after the deletion.

What is the cutoff score for the top : Students scoring in the top 18% get an A. What is the cutoff score for the top 18% in this example?

User Account

All Pages