# 演算法作業 六
###### tags: `演算法`
1. Suppose that in the rod-cutting problem of Section 15.1, we also had limit li on the number of pieces of length i that we are allowed to produce, for i = 1, 2, …, n. Design a DP algorithm for this problem.
Answer:
題目意思是每根棍子能產生長度i的線段的數量頂多只有l[i]
設定一個array D[i][j]，i代表最大能切出的長度，j代表rod的長度，D[i][j]儲存profit，每次都可以選擇要不要切出長度i的線段，但要切頂多切l[i]個，所以可以產生以下遞迴式
**初始值:** $D[i][0]=0、D[0][i]=p[i], 0\le i\le n$
**遞迴式:** $D[i][j]=max(D[i-1][j-i*k]+p[i]*k), \ 0\le k\le l[i] \ if \ j-k*i>0$
**解答:** $D[n][n]$
**時間複雜度:** $O(n^2k)$
**Pseudo code:**
```cpp=
input: p[],l[],n
Cut_Rod(p[],l[],n){
let D[0...n][0...n] be a new array
for i=0:n
D[i][0]=0
D[0][i]=p[i]
for i=1:n
for j=1:n
D[i][j]=0
for k=0:l[i]
if j-k*i>0
D[i][j]=max(D[i][j],D[i-1][j-k*i]+p[i]*k)
return D[n][n]
}
```
2. Not just any greedy approach to the activity‐selection problem produces a maximum‐size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. Do the same for the approaches of always selecting the compatible activity that overlaps the fewest other remaining activities and always selecting the compatible remaining activity with the earliest start time.
Answer:
(此題參考[https://walkccc.me/CLRS/Chap16/16.1/](https://))
第一種要挑選活動區間最短的，假設有三個活動分別是(1,5)、(4,7)、(6,12)，挑選第一個會是(4,7)，但這樣能挑的活動只有一個，實際上如果挑選(1,5)、(6,12)會是最佳解。
第二種是要挑衝突最少的，假設有11個活動分別是{(−1,1),(2,5),(0,3),(0,3),(0,3),(4,7),(6,9),(8,11),(8,11),(8,11),(10,12)}，照這個原則挑選選到(4,7)、(-1,1)、(10,12)，這樣只有三個活動，但事實上最佳解有四個。
第三種是要挑選開始時間最早的，假設有三個活動(0,5)、(1,3)、(4,6)，依照此原則會先選到(0,5)，然後就不能選了，但事實上最佳解有兩個活動(1,3)、(4,6)
3. Consider a modification to the activity-selection problem in which each activity $a_i$ has, in addition to a start and finish time, a value vi. The objective is no longer to maximum the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set A of compatible activities such that is maximized. Give a polynomial-time algorithm for this problem. (Hint: refer to Exercise 16.1-1)
Answer:
此題可以用dp解決，使用M[i]表示第1~i個活動所能得到的最大收益
M[i+1]是由決定要不要挑選第i+1個活動來決定的，如果不挑，那M[i+1]=M[i]，如果挑選，就要找到M[j]，此時第1~j個活動都跟第i+1個活動不衝突才能挑，找到這個j的時間可以在O(logn)之內，因為活動都已經用結束時間排序過一遍，並且搜尋的過程就像在一棵二元樹當中搜尋一樣。只有衝突或不衝突。並且會使用一個陣列$I[]$來記錄第i個活動有沒有在M[i]的解裡面
時間複雜度最糟是$O(n^2)$
**初始值:** $M_0=0、I_0=0$
**遞迴式:**
$M_i=max\{M_{i-1},M_j+v_i\}$
$I_i=\begin{cases}
0 \ if \ M_i=M_{i-1}\\
1 \ if \ M_i=M_j+v_i\\
\end{cases}$
**解答:** $M_n$
**pseudo code:**
```cpp=
Input:s[],f[],v[],n
Act_select(s[],f[],v[],n){
M[],I[];//創建新陣列
M[0]=0
I[0]=0
for i=1:n
M[i]=M[i-1]
I[i]=0
for j=i-1:1
if I[j]==1 and s[i]>=f[j]
if M[j]+v[i]>M[i-1]
M[i]=M[j]+v[i]
I[i]=1
break
return M[n]
}
```
另一個方法是對所有s[]、f[]做前處理，可以將時間複雜度壓到$O(n)$ (如果不算sorting時間的話)
$I[]$用來儲存端點
$P[]$用來儲存在第i個活動前最靠近i且compatible的活動
也就是說P[i]就是j(對應以上遞迴式)
```cpp=
Act_select(s[],f[],v[],n){
let M[],I[],P[] be new arrays
put s[],f[] in I[]
sort(I[],2n)
j=0;
for i=1:2n
if I[i] is start time
P[I[i].index]=j
if I[i] is end time
j=I[i].index
for i=1:n
M[i]=max(M[P[i]]+v[i],M[i-1])
return M[n]
}
```
4. Given a 0-1 knapsack problem with the knapsack size K and n items, where each item has its weight in integer and its value in real.
a. Design an algorithm to find the most valuable load of the items that fit into the knapsack.
b. Design a pseudo-polynomial time algorithm to determine the optimal solution that the total weight exactly equals to K.
Answer:
a. 使用dp來解此題，用P[][]陣列來儲存答案，P[i][j]代表背包容量j的情況下，挑選第1~i個物品能組成的最大利益。
W代表背包容量，總共n個物品
時間複雜度是$O(nW)$
**初值:** $P[0][1:W]=0、P[1:n][0]=0$
**遞迴式:** $P[i][j]=\begin{cases}
max\{P[i-1][j],P[i-1][j-w[i]]+v[i]\} \ if \ w[i]\le j\\
P[i-1][j]\\
\end{cases}$
**解答:** $P[n][W]$
**pseudo code:**
```cpp=
Input: w[],v[],n,W
ZeroOne(w[],v[],n,W){
P[][];//創建一陣列
for i=1:W
P[0][i]=0
for i=1:n
P[i][0]=0
for i=1:n
for j=1:W
if w[i]<=j
P[i][j]=max(P[i-1][j],P[i-1][j-w[i]]+v[i])
else
P[i][j]=P[i-1][j]
return P[n][W]
}
```
b. 加開一個陣列A[][]，A[i][j]表示在前i個物品的重量能不能組成j這個重量，如果可以才計算P[i][j]，不行的話代表P[i][j]是0
時間複雜負是:$O(n*W)$
**初值:** $P[0][1:W]=0、P[1:n][0]=0、A[0:n][0]=1、A[0][1:W]=0、A[i:n][w[i]]=1$
**遞迴式:**
$A[i][j]=\begin{cases}
A[i-1][j-w[i]] \ or \ A[i-1][j] \ if \ w[i]\le j\\
A[i-1][j]\\
\end{cases}$
$P[i][j]=\begin{cases}
max\{P[i-1][j],P[i-1][j-w[i]]+v[i]\} \ if \ w[i]\le j\\
P[i-1][j]\\
0 \ if \ A[i][j]==0\\
\end{cases}$
**解答:** $P[n][W]$
**pseudo code:**
```cpp=
Input: w[],v[],n,W
ZeroOne(w[],v[],n,W){
P[][]={},A[][]={0};//創建陣列，將陣列元素全部設為0
A[0][0]=1
for i=1:W
P[0][i]=0
A[0][i]=0
for i=1:n
P[i][0]=0
A[i][0]=1
for j=i:n
A[j][w[i]]=1
for i=1:n
for j=1:W
if w[i]<=j
A[i][j]=A[i-1][j-w[i]] or A[i-1][j]
if A[i][j]==1
P[i][j]=max(P[i-1][j],P[i-1][j-w[i]]+v[i])
else
A[i][j]=A[i-1][j]
if A[i][j]==1
P[i][j]=P[i-1][j]
return P[n][W]
}
```
第二個作法是改變初始值，如果不能剛好組成k就是負無限大
**初值:** $D[i][0]=0$
$D[0][i]=-INF$ if i>0
剩下就跟原先的01背包一樣
5. Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate m miles before running out of water. (Because North Dakota is relatively flat, the professor does not have to worry about drinking water at a greater rate on uphill sections than on flat or downhill sections.) The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations.
The professor’s goal is to minimize the number of water stops along his route across the state. Give an efficient method by which he can determine which water stops he should make. Prove that your strategy yields an optimal solution, and give its running time
Answer:
假設總共有n個站，包括起點終點，每站的位置以r[]儲存，總共有n個站，可以用greedy algorithm解決這題，每次都盡量前進越多站越好，如果裝滿水後可以最遠可以到第i個站，就把第i個站紀錄起來，總共經過的站數就是解答
時間複雜度是O(n)
```cpp=
Input:r[],n,m
global variable: Stops[] //一個vector
Func(r[],n,m){
Stops.clear()//清空該vector
init=r[1]
dis=0
for i=2:n
dis=r[i]-init
if dis>m
Stops.push_back(i-1)
init=r[i-1]
i=i-1//要倒退一個站，下個迴圈才會算到r[i]-r[i-1]
return Stops.size()
}
```
6. Show how to solve the fractional knapsack problem in O(n) time.
Answer:
先將每個物品的單位重量價格計算出來並放入array，接著找array的中位數，用課本9-3的方法可以在O(n)時間內找出，並把所有大於中位數的物品重量加起來，也就是M，如果M>=W，那我們要解的問題就是如何在大於中位數的物品當中挑選物品放入背包，問題大小剩下n/2，如果M<W，那大於中位數的物品一定會全拿，背包容量剩下W-M，再解如何在小於中位數的物品當中挑選物品放入背包容量W-M的背包，問題大小也剩n/2
寫成遞迴式可以表示為T(n)=T(n/2)+O(n)
透過master theorem可以解得T(n)=O(n)
```cpp=
Input:p[],w[],W,n //p[i]代表第i個item的價格，w[i]代表重量
//W為背包的容量，n為item種類的數量
global varialbe: sum,p[],w[]A[],n//平均價格A[i]=p[i]/w[i]
funct(p[],w[],W){
sum=0;
for i=1:n
A[i]=p[i]/w[i]
return Frack(A[],1,n,W);
}
Frack(A[],start,end,W){
if W==0
return 0
if start==end and W!=0
if W>=w[start]
return p[start]
else
return W*A[start]
med=med_of_med(A[],start,end);//O(n)
M=0;med_sum=0;
for i=start:end
if A[i]>A[med]
M+=w[i]
med_sum+=p[i]//所有大於med的物品價格加起來
if M>=W
sum+=Frack(A[],med,end,W);
else
sum+=med_sum;
sum+=Frack(A[],start,med,W-M);
return sum;
}
```
7. Generalize Huffman's algorithm to ternary codewords (i.e., codewords using the symbols 0, 1, and 2), and prove that it yields optimal ternary codes.
Answer:
原本的huffman code是建構binary tree，現在我們建構的是ternary tree，過程如下
(1) 將字母依照frequency大小排序好(用MIN HEAP)
(2) 檢查這些字母個數%2有沒有等於0，等於0就在最尾端插入一個NULL字元frequency等於0
(3) 產生一新節點x
(4) 執行一次Extract_Min得到一節點，成為x的左子節點
(5) 執行一次Extract_Min得到一節點，成為x的中間子節點
(6) 執行一次Extract_Min得到一節點，成為x的右子節點
(7) x的frequency為3個子節點的frequency相加。
(8) 只要MIN HEAP不是空的，就將x插入MIN HEAP中並重複步驟(2)~(7)。
```cpp=
Ternary_Huffman(C[],n){
if n%2==0
C[n+1]=0
n=n+1
Q=Build_MinHeap(C[],n)
while(Q.size()!=1)
let p be a new node
p.left=Q.Extract_Min()
p.middle=Q.Extract_Min()
p.right=Q.Extract_Min()
return Q.Extract_Min()
}
```
證明分為兩部分，第一部分是證明一個字母集的optimal ternary trees中一定包含著最低frequency的三個字母是深度最深的三個樹葉節點這樣的optimal ternary tree。第二部分是證明將三個frequency最小的節點結合成一個新節點的optimal ternary tree就是原本的optimal ternary tree將最小的三個節點拿掉並加入這個新的節點
**proof:**
假設T為C字母集的optimal ternary tree，n為C字母的個數，如果n整除2，那無法以C的字母做為leaf node建構一個ternary tree，所以此時在C內加入一個NULL字元frequency為0。
假設T的最底層三個節點為a,b,c，而最低freq的三個節點為x,y,z，將a和x互換得到新的ternary tree T'，B(T)-B(T')=(a.freq-x.freq)($d_T(x)-d_T(a)$) >=0，將b和y互換得到T''，將c和z互換得到T'''，可推得B(T')>=B(T''')，且T為optimal所以B(T)<=B(T''')，所以B(T)=B(T''')，所以永遠存在三個freq最小的節點在最底層的optimal ternary tree。
假設T'為將x,y,z合併成一新節點p的optimal ternary tree，B(T)=B(T')+x.freq+y.freq+z.freq，假設T並非optimal ternary tree for C，假設T''才是，那B(T'')=B(T''')+x.freq+y.freq+z.freq <B(T)
所以B(T''')<B(T')，和我們先前假設T'為C去除x,y,z加入p的optimal ternary tree矛盾，所以T一定是C字母集的optimal ternary tree
所以依照此方法建立的optimal ternary tree是correct。
8. Find the Huffman codes of the data given below by drawing the tree like the figure 16.5 in the page 432. You should write down each step of the Huffman’s algorithm.
a:22 b:2 c:5 d:3 e:5 f:8 g:7 h:11
Answer:
(1) 將字母依照frequency大小排序好(用MIN HEAP)
(2) 產生一新節點x
(3) 執行一次Extract_Min得到一節點，成為x的左子節點
(4) 執行一次Extract_Min得到一節點，成為x的右子節點
(5) x的frequency為兩個子節點的frequency相加
(6) 只要MIN HEAP不是空的，就將x插入MIN HEAP中並重複步驟(2)~(5)。
Sign in with Wallet
Connect another wallet