Reference no: EM1361440
Let An = {a1, a2, ... , an} be a finite set of distinct coin types (for example a1 = 50 cents, a2 = 25 cents, a3 = 10 cents, and so on.) We can assume each ai is an integer and a1 > a2 > ... > an. Each type is available in unlimited quantity. The coin-changing problem is to make up an exact amount C using a minimum total number of coins. C is an integer > 0.
a) Show that if an ≠ 1, then there exists a finite set of coin types and a C for which there is no solution to the coin-changing problem.
b) Show that there is always a solution when an = 1.
c) When an = 1, a greedy solution to the problems makes change by using the coin types in order a1, a2, ... , an. When coin type ai is being considered, as many coins of this type as possible are given. Write an algorithm based on this strategy. Show that this algorithm doesn't necessarily generate solutions that use the minimum total number of coins.
d) Show that if An = {kn-1, kn-2, ... , k0} for some k > 1, then the greedy method of part
(c) always yields solutions with a minimum number of coins.
|
Explain how does the price of fertilizer compare
: Explain how does the price of fertilizer compare to the average total cost, the average variable cost, and the marginal cost of producing fertilizer.
|
|
Find the acceleration of the bucket
: suppose that the springs have somehow not yet compressed to their maximum amount. How much are the springs compressed.
|
|
Calculate company margin of safety
: Van Roekel Corporation sells a single product. The product has a selling price of $100 each unit and variable expenses of 80 percent of sales. If the company's fixed expenses total $150,000 each year,
|
|
Disease prevention strategies
: Should healthcare organizations develop disease prevention strategies? Why or why not? Do you think ethically it is their responsibility?
|
|
There exists finite set of coin types-coin-changing problem
: Show that if an ≠ 1, then there exists a finite set of coin types and a C for which there is no solution to the coin-changing problem. Show that there is always a solution when an = 1.
|
|
Illustrate what would be the size of the us labor force
: Suppose that the U.S. noninstituional adult population is 230 million and the labor force participation rate is 67 percent. Illustrate what would be the size of the U.S. labor force.
|
|
Solving finance related problems
: In a statement of cash flow, the term cash includes, The ownership of common stock in a corporation usually carries the following rights:
|
|
Describe the profit-maximizing amounts of electricity
: Describe the profit-maximizing amounts of electricity to produce at the two facilities, the optimal price, and the utility company's profits.
|
|
How college receive payments
: The college has annual fixed costs of $10 million, and the variable cost for each additional student is $5,000. To continue operating, the college must receive payments equal to its total costs.
|