16-1 Coin changing

Consider the problem of making change for \(n\) cents using the fewest number of coins. Assume that each coin's value is an integer.

a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.

b. Suppose that the available coins are in the denominations that are powers of \(c\), i.e., the denominations are \(c^0, c^1, \ldots, c^k\) for some integers \(c > 1\) and \(k \ge 1\). Show that the greedy algorithm always yields an optimal solution.

c. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of \(n\).

d. Give an \(O(nk)\)-time algorithm that makes change for any set of \(k\) different coin denominations, assuming that one of the coins is a penny.

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 \(0\).

b. Given an optimal solution \((x_0, x_1, \dots, x_k)\) where \(x_i\) indicates the number of coins of denomination \(c_i\) . We will first show that we must have \(x_i < c\) for every \(i < k\). Suppose that we had some \(x_i \ge c\), then, we could decrease \(x_i\) by \(c\) and increase \(x_{i + 1}\) by \(1\). This collection of coins has the same value and has \(c − 1\) fewer coins, so the original solution must of been non-optimal. This configuration of coins is exactly the same as you would get if you kept greedily picking the largest coin possible. This is because to get a total value of \(V\), you would pick \(x_k = \lfloor V c^{−k} \rfloor\) and for \(i < k\), \(x_i\lfloor (V\mod c^{i + 1})c^{-i} \rfloor\). This is the only solution that satisfies the property that there aren't more than \(c\) of any but the largest denomination because the coin amounts are a base \(c\) representation of \(V\mod c^k\).

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

d. See algorithm \(\text{MAKE-CHANGE}(S, v)\) which does a dynamic programming solution. Since the first forloop runs \(n\) times, and the inner for loop runs \(k\) times, and the later while loop runs at most \(n\) times, the total running time is \(O(nk)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用