---
# System prepended metadata

title: 'HW7 - Q6 c, d'
tags: [109-2, 演算法]

---

# HW7 - Q6 c, d
###### tags: `演算法`, `109-2`

:::success
https://hackmd.io/@Cing-Chen/rJRJunMrO
:::

## Question
**Problem 16-1**
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, ..., c^k for some integers c>1 and k≥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.


## Mein Answer

### c. 
好棒，我最喜歡舉反(ㄔㄞ)例(ㄊㄞˊ)了！
好的，假設我們想把 48763 塊錢找開，而我們有面額 1, 4433, 46969 元的銅板。
照 Greedy 解，我們會拿 1 個 46969 元、和 1794 個 1 元銅板
但最佳解，我猜各位星爆廚們都看的出來，當然拿 11 個 4433 塊的銅板啊！

### d.
O(nk)...你分明就是要我用 DP 去解嘛！

```=
/// ===輸入===
/// d: 面額的陣列
/// n: 要求的$$
/// ===結果===
/// S: 結果-面額陣列
/// C: 結果-數量陣列

C[0] = 0
C[1~d.length] = MAX
for i in (1, n):
    for j in (1, d.length):
        if d[j] <= i:
            if C[i-d[j]]+1 < this_min
                this_min = C[i-d[j]]+1
                this_coin = j
    C[i] = this_min
    S[i] = this_coin
```