###### tags: `Algorithm` `test` `thu`
{%hackmd theme-dark %}
# CH15

## Exercise

### 15.1-1
### Show that equation $(15.4)$ follows from equation $(15.3)$ and the initial condition $T(0) = 1$.
$$(15.3) => T(n) = 1 + \sum_{j=0}^{n-1}T(j)$$
$$(15.4) => T(n) = 2^n$$
PS.直接寫出來會死484
$$T(n) = 1 + \sum_{j=0}^{n-1}2^ｊ$$
使用級數和公式
$$T(n) = 1 + \frac{2^n - 1}{2-1}$$
$$ T(n) = 2 ^n $$

### 15.1-2
### Show ...
題意大概是每次都用貪心的方法去做，但是不一定是最佳解
每個長度$(1 \le i \le n )$都有個單位最高價值比$Pi / i$ 稱為 $density$
The greedy strategy 會將n長度的rod切下一塊$density$最高的，剩下的也這樣去做

Let p1 = 0, p2 = 4, p3 = 7 and n = 4.
因為p3/3=7/3=2.333...的$density$最高,第一塊切在length=3
剩下長度為1的不能切了,它的價值又是0,所以收益為7
但是如果用最佳化結果切在length=2,收益為8

### 15.1-3
### Show ...