<style>
* {
letter-spacing: 0.02em;
text-align:justify
}
p.part {
text-indent: 2em;
line-height: 2em;
}
.keyword {
color: #03A9F4;
}

.variable {
color: red;
border-radius: 10%;
margin: 1px;
padding: 1px 5px;
background: #f5f5f5;
font-weight: 480;
}

.not-indent{
text-indent: 0;
line-height: 0;
}
p .small {
text-indent: 0em;
line-height: 0em;
}
</style>

# Rods-cutting Problem

## Introduction
Rods-cutting Problem描述給定長度為$n$ inches的長竿與各個inches所能賣出的價格$p_i\text{ for i = 1, 2, ..., n}$，找出將長竿切成數份分別賣出所能獲得的最大收益。
>Given a rod of length n inches and a table of prices p~i~ for i=1,2,...,n, determine the maximum revenue r~n~ obtainable by cutting up the rods and selling the prices

## Content
---

### 1. Observation
假設$n=4$則切法總共有 $2^{n-1} = 2^3 = 8$ 種(包含重複)，如下圖(a)~(h)所示。然而實際上的不重複的切法只有(a)、(b)、\(c\)、(e)、(h)，其不重複切法總數可用<span class="keyword">**partition function**</span>表示，其近似值為$e^{\pi\sqrt{2n/3}}/4n\sqrt{3}$。雖然實際不同切法小於$2^{n-1}$，但其數量仍遠大於polynomial $n$。

要尋找最大收益之前，先觀察$r_1\text{ ~ }r_{10}$的最佳解有甚麼特性，不難發現每個的最佳解都是更小問題的最佳解所組成，例如:在窮舉4 inches所有切法中圖\(c\) $r_4=r_2+r_2=5+5=10$ 由2 inches的最佳解組成，從結果來看這是合理的，因為將4 inches切一半，我們並不知道2 inches是否要繼續切下去，故我們需要求的2 inches 最佳解才可以解出4 inches的答案。<br>

有沒有可能當前問題最佳解(Optimal solution)並不是由子問題最佳解組成，我們可以使用矛盾證法來看，假設存在不是由最佳解組成，代表至少有一部分x inches能夠獲取比x inches的最佳解更多收益，但並不屬於x inches的最佳解，此論點產生矛盾，故我們可以肯定rods-cutting problem的最佳解是由子問題的最佳解組成，如此的特性稱之為<span class="keyword">**optimal substructure**</span>。

>optimal solutions to a problem incorporate optimal solutions to related
subproblems, which you may solve independently

我們可以窮舉每個切法對對應的收益取最大值，並將與子問題最佳解關係表示如下$r_n=max\{p_n,r_1+r_{n-1},r_2+r_{n-2},...,r_{n-1}+r_1\}=max\{p_i+r_{n-i}:1\le i\le n\}$，其中 $p_0$ 代表不切所能獲得最大收益、$r_1+r_{n-1}$ 代表切成 1 inch和 n-1 inches...以此類推。如上圖例子$n=4$，圖(a)~(h)的收益加總最大的為圖\(c\)，故$r_4=10$為所求。<br>

### 2. Recursive method
\begin{aligned}
Cut\_rod(p, n) =
\begin{cases}
0&\text{, if }n=0\\
max\{\, p_i\,+\,Cut\_rod(p, n-i): 1\le i \le n\}
&\text{, if }n \ge 1
\end{cases}
\end{aligned}

int cut_rod(vector<int>& p, int n) {
    if (n == 0) {
        return 0; // base case
    }
    
    int q = INT_MIN;
    for (int i = 1; i <= n; i++) {
        q = max(q, p[i] + cut_rod(p, n-i)); 
    }
    
    return q;
}

利用遞迴解法，其Base case為當 $n=0$ 時收益為0，當$n \ge 1$ 時，則檢查所有可能切法取得最大收益。

上述程式<span class="variable">cut_rod</span>的呼叫次數隨著$n$增加成指數增長，並具以下關係
\begin{aligned}
T(n)=
\begin{cases}
1+\sum_0^{j-1}T(j)&\text{, if }n\ge 1\\
1&\text{, if }n=0
\end{cases}
=2^n, \text{ for }n\ge0
\end{aligned}

由<span class="variable">cut_rod</span>呼叫次數來看，這樣的解法不可行的，當$n=40$電腦將會跑數分鐘之久，故嘗試優化Recursive method使時間複雜度降到polynomial time

### 3. Top-down with memoization (optimal recursive)
我們將$n=4$的recursive tree畫出發現每次呼叫都會求解重複的sub-problem，故使用memoization紀錄求解答案，當要使用時直接回傳，此種方法使用了<span class="keyword">**time memory trade-off**</span>概念，表以空間換時間。

int memoized_cut_rod(vector<int>& p, int n) {
    // use memory to record the subproblem answer
    vector<int> r(n+1, -1);
    
    // solve the problem
    return memoized_cut_rod_aux(p, n, r);    
}

int memoized_cut_rod(vector<int>& p, int n, vector<int>& r) {
    if (r[n] >= 0) {
        return r[n]; // already have a solution for length n, then return
    }
    
    if (n == 0) {
        q = 0;
    }
    else {
        q = -1;
        for (int i = 1; i <= n; i++) { // i is the position of the first cut
            q = max(q, p[i] + memoized_cut_rod_aux(p, n-i, r));
        }
    }
    r[n] = q;  // remember the solution value for length n
    return q;
}

$\text{Time complexity: }\Theta(n^2)$

$\text{Space complexity: }O(n)$

### 4. bottom-up with memoization (iterative)
另一個解法為bottom-up method，其觀點為既然解大問題之前需先解決小問題，不如先把小問題先解決，再組合成大問題的答案

int buttom_up_cut_rod(vector<int>& p, int n) {
    vector<int> r(n+1, -1); // remember solution values in r
    r[0] = 0;
    
    for (int i = 1; i <= n, i++) { // for increasing rod length i
        r[i] = -1;
        
        for (int j = 1; j <= i; j++) { // j is the position of the first cut
            r[i] = max(r[i], p[i] + r[j-i]); 
        }
    }
    
    return r[n];
}

$\text{Time complexity: }\Theta(n^2)$

$\text{Space complexity: }O(n)$

:::success
:bulb:關於top-down與bottom-up的差別請參考上一篇Basic Dynamic Programming
:::

### 5. Subproblem graphs
在解Dynamic Programming Problem時，必須了解subproblem的相依關係才可使用，未確認相依關係，可利用Subproblem graph來了解問題結構。

如上圖所示，$n=4$的問題可畫成一有向圖$G(V,E)$並且該圖是**acyclic**(無環圖)，並不會有child的optimal solution相依於parent optimal solution，其概念相似於topological order，故Dynamic Programming擁有另外一種定義，若問題可被表示為一連串決策過程(Directed Acyclic Graph 有向無環圖)即可用Dynamic Programming。
>Dynamic Programming is an algorithm design method that can be used the solution to a problem may be viewed as the result of a sequence of decisions.

---
### Reference

<span class="not-indent">
[1] Introduction to Algorithm (Fourth Edition), Cambridge, Massachusetts London, England<br>
[2] Inroduction to the design and analysis of algorithms, R. C. T.Lee, S. S. Tseng, R.C. Chang, Y. T. Tsai
</span>

---

<br>

>[name=Sky]
###### tags: `Algorithm` `Dynamic Programing`