Week 7

Click to Open TOC

• Week 7
• Question
• Answer
  • Q1
  • Q2
  • Q3
  • Q4
    • a小題，設計演算法
    • b小題，讓total weight剛好等於K
  • Q5
  • Q6
  • Q7
  • Q8

Question

Click to Open Question

Check

• Q1
• Q2
• Q3
• Q4
• Q5
• Q6
• Q7
• Q8

Answer

Q1

• Mark

Example

Length i	1	2	3	4
Price Pi	15	20	33	36
Limit Li	2	1	1	1

Example : length = 4
4 => 36
1,3 => 48
2,1,1 => 50 best

最優子結構解法：
1,1,1,1 => 60

在有 Limit Li 的限制下，rod cutting problem將子問題獨立解決(如ex.會超出limit限制)，所以最優子結構不存在。

蘇都扣

// p[i] = price of length i rod
// l[i] = limit of length i rod
// dp[i][j] = the max value of n rod

limit_length_rod_cutting(p, l)
    create array dp[i][j]
    
    for i = 0 to n
        dp[i][0] = 0
        
    for j = 1 to n
        dp[0][j] = -INFINITY
    
    for i = 1 to n
        for j = 1 to n 
            for k = 1 to l[i]
                if(k = 1 && (j - i * k)< 0)
                    dp[i][j] = dp[i - 1][j]
                    break; //後面必定為負，先行跳出
                else if (j - i * k) < 0
                    break; //在下面那個else if已經求出dp[i][j]的最大值
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - i * k] + p[i] * k)
    return dp[n][n]

遞迴式

$dp[i][j]\mathrm{為}\mathrm{在}\mathrm{可}\mathrm{切}\mathrm{割}\mathrm{長}\mathrm{度}\mathrm{為}i\mathrm{的}\mathrm{情}\mathrm{況}\mathrm{下}，\mathrm{當}\mathrm{前}j\mathrm{長}\mathrm{度}\mathrm{的}\mathrm{最}\mathrm{大}profit$

$\begin{array}{rl}dp[i][j{]}_{0\le i,j\le n}& =\{\begin{array}{l}\text{0 if j=0 }\\ -\mathrm{\infty }\text{ if j!=0, i=0}\\ ma{x}_{0\le l\le lim[i]}\{dp[i-1,j-i\ast l]+p[i]\ast l\},if1\le i,j\le nand0\le j-i\ast l\end{array}\end{array}$

所求：

$dp[n][n{]}_{\mathrm{\#}}$

Q2

• xian

【The approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work.】

Activity $a_i$	1	2	3
Start $s_i$	6	5	1
Finish $f_i$	10	8	6
Duration	4	3	5

Greedy:

$a_2$
Optimal:

$a_1、a_{3}contradtio{n}_{\mathrm{\#}}$

【The approaches of always selecting the compatible activity that overlaps the fewest other remaining activities】

Activity $a_i$	1	2	3	4	5	6	7	8	9
Start $s_i$	0	0	1	2	3	4	5	5	6
Finish $f_i$	2	3	3	4	5	6	7	7	8
# of overlapping activities	2	3	3	3	2	3	3	3	2

Greedy:

$a_1、a_5、a_9$
Optimal:

$a_1,a_4,a_6,a_{9}contradtio{n}_{\mathrm{\#}}$

【The approaches of always selecting the compatible remaining activity with the earliest start time.】

Activity $a_i$	1	2	3	4
Start $s_i$	2	1	3	5
Finish $f_i$	4	8	4	7
earliest start time	2	1	3	5

Greedy:

$a_2$
Optimal:

$a_1、a_{4}contradtio{n}_{\mathrm{\#}}$

Q3

• yee

【題目】

Consider a modification to the activity-selection problem in which each activity

$ai$ 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

$\sum _{a_k\in A\vee k}$ is maximized. Give a polynomial-time algorithm for this problem. (Hint: refer to Exercise 16.1-1)

【解題思路】

透過DP來解此題，主要要思考如何找到合適的最佳解，並且老師說時間複雜度要到

$O(nlogn)$，所以用何種方法找就蠻重要的，於是我採用bottom-up的方式來做，並且用BinarySearch來降低找最佳解的時間。

【遞迴式】

$$\begin{gathered} p[0]=0 \\ p[j{]}_{1\le j\le n}=max\{\begin{array}{l}p[j-1]\\ p[i{]}_{i<=j,a_i\in A}+v_j\end{array} \end{gathered}$$

【蘇都扣】

int A[];
sort(A,cmp_finish_time);//將A集合以完成時間由小到大排序
int start_time[];//宣告一陣列用來存開始時間
sort(start_time,cmp_start_time);//以開始時間由小到大排序

int dp[]; 
int solution[]//宣告一陣列存放最佳解索引值
for i from 1 to A_length:
    solution[i] = binarySearch(start_time,A[i].start) - 1;

//dp建表
dp[0] = 0;
for i from 1 to A_length
    dp[i] = max(dp[i - 1],dp[solution[i]] + A[i].value);
    
//ans = dp[dp_length]

【複雜度】

$Time$ : 兩次排序所花時間為

$2nlogn$ 加上

$forloop$乘上一次

$binarySearch$ 所花時間為

$nlogn$ 加DP建表時間

$n$ ,總時間複雜度為

$O(nlogn)$

$Space$ : 多建了三個陣列來記錄

$(start\mathrm{\_}time,dp,solution)$ 因此空間複雜度為

$O(n)$

【C++實作】(舊版) 新版待補

#include<iostream>
using namespace std;


struct activity{
    int start;
    int finish;
    int value;
};

int binarySearch_change(int array_length,int array[],int key);
int binarySearch(int array_length,int array[],int key);
void QuickSort(int arrays[],int left, int right);
int main(){

    int num_activity;
    cin >> num_activity;

    activity activities[num_activity + 1];
    int start_array[num_activity + 1];
    
    for(int i = 1; i <= num_activity; i++){
        cin >> activities[i].start >> activities[i].finish >> activities[i].value;
        start_array[i] = activities[i].start;   
    }
    QuickSort(start_array,1,num_activity);
    int j = binarySearch_change(num_activity,start_array,activities[1].finish);

    printf("j = %d\n",j);
    int dp_length = num_activity + j, dp[dp_length];
    for(int i = 0; i < j; i++)
        dp[i] = 0;

    for(int i = 1; i <= num_activity; i++){
        int solution_index = binarySearch(num_activity,start_array,activities[i].start);
        printf("solution_index = %d\n",solution_index);
        dp[j] = max(dp[j - 1],dp[solution_index] + activities[i].value);
        j++;
    }

    for(int i = 1; i < dp_length; i++)
        printf("%d ",dp[i]);

}
int binarySearch_change(int array_length,int array[],int key){
    int left = 1, right = array_length;
    int mid;
    while (left <= right){
        mid = (left + right) / 2;

        if(left == right){
            if(key > array[mid])
                return mid + 1;
            else
                return mid;
        }

        if(key > array[mid])
            left = mid + 1;
        else if(key < array[mid])
            right = mid -1;
        else
            return mid + 1;

    }
    
    return -1;
}

int binarySearch(int array_length,int array[],int key){
    int left = 1, right = array_length;
    int mid;
    while (left <= right){
        mid = (left + right) / 2;

        if(key > array[mid])
            left = mid + 1;
        else if(key < array[mid])
            right = mid -1;
        else
            return mid ;

    }
    
    return -1;
}

void QuickSort(int arrays[],int left, int right){
    int i, j, pivot;
    if(left < right){
        i = left;
        j = right + 1;
        pivot = arrays[left];
        do{
            do
                i++;
            while(arrays[i] < pivot);
            do 
                j--;
            while(arrays[j] > pivot);
            if(i < j){
                int temp = arrays[i];
                arrays[i] = arrays[j];
                arrays[j] = temp;
            }
        }while(i < j);
        int temp = arrays[left];
        arrays[left] = arrays[j];
        arrays[j] = temp;
        QuickSort(arrays,left,j - 1);
        QuickSort(arrays,j + 1,right);
    }
}
/*
1 2 50
3 5 20
6 19 100
2 100 200
*/

Q4

• songchiu

a小題，設計演算法

解題方式：透過DP來解

【用到的變數】

• 二維陣列
  $P[i,k]$
  
  $i$為要裝前幾個進背包；
  $n$為總共有幾個內容物(
  $0\le i\le n$)
  
  $k$為背包的容量；
  $K$為背包的最大容量(
  $k\le K$)
• 背包內容物的大小
  ${\text{w}}_i$ (
  $k>w_i$)
• 背包內容物的價值
  ${\text{v}}_i$

【遞迴式】

$P[0,k]=0,k>0$

$P[i,0]=0,i\ge 0$

$P[i,k]=max\{P[i-1,k],P[i-1,k-w_i]+v_i\}$ (

$0\le i\le n,k\le K$)

【蘇都扣】

for i from 1 to n
    for k from 1 to K
        if k < w[i] then
            P[i][k] ⟵ P[i-1][k]
        else
            P[i][k] ⟵ max(P[i-1][k], P[i-1][k-w[i]] + v[i])
return P[n][K]

【題目所求的解答】
即是該

$P$陣列最右下角的元素

$P[n][K]$

【時間複雜度】

$O(nK)$

b小題，讓total weight剛好等於K

跟a小題的方式很類似，但要針對初始值進行一點修改
這樣就可以確保DP表格的資料，只有在「剛好拿滿特定值」時，才會被存進去

【遞迴式】

$DP[i,k]=\{\begin{array}{ll}-\mathrm{\infty }& \text{if }i=0\text{ and }k>0\\ 0& \text{if }k=0\\ max\{DP[i-1,k],DP[i-1,k-w_i]+v_i\}& \text{if }k\ge w_i\\ DP[i-1,k]& \text{otherwise}\end{array}$

【蘇都扣】

for i from 0 to n
    for k from 0 to K
        if k = 0
            DP[i][k]=0
        else if i=0 and k>0
            DP[i][k]=-INFINITY
        else if k >= w[i] then
            DP[i][k] ⟵ max(DP[i-1][k], DP[i-1][k-w[i]] + v[i])
        else
            DP[i][k] ⟵ DP[i-1][k]

return DP[n][k];

【時間複雜度】

$O(nK)$，但是

$K$有可能會

$>2^n$，所以是個pseudo-polynomial time algorithm

Q5

• chung

【題目】

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.

【解題思路】

此題採用Greedy Approach，每次先確認剩餘水量是否可以到達下一個補水站，如果可以就跳過繼續走，反之則停留裝水

【證明】

【Prove Optimal Substructure】
假設總共有n個補水站，s是最佳補水次數。令k為最佳解的第一個補水站，可分為k和n-k兩個子問題，n-k個補水站中補了s-1次水，若在這個子問題中存在更好的最佳解，則最佳補水次數會小於s，與當初假設矛盾，故得證。

【Prove Greedy-Choice Property】
假設在起點m英里範圍內有n個補給點。 Greedy-Choice解決方案選擇第k個位置作為其第一站，第k個位置以外的點都不能作為第一站，因為Professor Gekko會先把水用完，如果一個解法是選擇j<k的位置作為第一站，則Professor Gekko仍可以選擇第k個位置，使得他離開k點時，水至少和他選擇第j個位置一樣多，因此，如果他選了第k點作為第一站，他可以走到同樣遠的地方而不需增加加水次數，故可證明每次到最遠的地方加水是最佳解。

【蘇都扣】

MinimumWaterStop (available_spot)
    distance=0;
    for each spot in order
        if distance + distance_to_next_spot > m mile
            nunber_of_water_stops++;
            distance = distance_to_next_spot; //各位這裡應該改成distance = distance_to_next_spot
        else
            distance += distance_to_next_spot;
    return nunber_of_water_stops

時間複雜度 = O(n)

Q6

• chung

【題目】

Show how to solve the fractional knapsack problem in O(n) time.

【解題思路】

Fractional Knapsack Problem中物品可以被切割，取物時可只取部分比例。此題採用Greedy Approach，優先取出單位價值(價值與重量的比值)最高的物品，直到背包無法裝入為止。

【解題步驟】

假設W是背包容量，R是所有物品的性價比

1. 從R中找出中位數r
2. 將除了r以外的元素分成以下三種:
   • $R_1=\{p_i/w_i|p_i/w_i>r,for1\le i\le n\},W_1=\sum _{i\in R_1}{w}_i$
   • $R_2=\{p_i/w_i|p_i/w_i=r,for1\le i\le n\},W_2=\sum _{i\in R_2}{w}_i$
   • $R_3=\{p_i/w_i|p_i/w_i<r,for1\le i\le n\},W_3=\sum _{i\in R_3}{w}_i$
3. $$\begin{gathered} if{W}_1>W \\ \text{then recurse on R1 and return the computed solution.} \\ else \\ while\text{(there is space in knapsack and R2 not empty)} \\ \text{add items from R2} \\ if\text{(knapsack is full)} \\ \text{return items from R1 + the items just added from R2} \\ else \\ \text{reduce knapsack capacity by W1 + W2,} \\ \text{recurse on R3 and return the items in R1 + R2.} \\ \text{return items from R1 and R2 + the items just added from R3} \end{gathered}$$

【分析】

Find the ratio(profit/weight)= O(n) time, then find the median item(using selection procedure).The median of medians algorithm returns the median of a given array in time O(n). The recurrence here is T(n)=T(n/2)+O(n), and we have that T(n)=O(n).

【蘇都扣】

get_optimal_value(array Weight, array Ratio, int capacity)
    for i <- 1 to size (Weight){
        if (capacity == 0) return totalValue
        double a = Weight[i] < capacity ? Weight[i] : capacity;
        totalValue = totalValue + a * Ratio[i];
        Weight[i] = Weight[i] - a;
        capacity = capacity - a;
    }
    return totalValue,capacity

linear_fractional_knapsack (array Weight, array Value, int capacity)
    for i <- 1 to size (Value)
        ratio[i] <- Value[i] / Weight[i]
    find median element R
    The R1, R2, R3 are subsets of the ratio set being <, = or > than R.
    The W1, W2, W3 are the summation of the weights of these sets.
    if (W1 > Weight)
        [total1, capacity1] = get_optimal_value(W1, R1, capacity)
    else
        while (capacity1 != 0 && R2 != empty)
            [total2, capacity2] = get_optimal_value(W2, R2, capacity1)
        if (capacity2 != 0)
            [total3, capacity3] = get_optimal_value(W3, R3, capacity2)   
    return total1 + total2 + total3

【Quick select(快速選擇)】

快速選擇(Quickselect)是一種選擇元素的演算法，利用Quick Sort演算法，在排序序列的同時，選擇出序列中第K小或是第K大的元素。若我們只想要從序列中找出一個第K小或是第K大元素，使用Quickselect會比使用Quick Sort來得快很多，因為前者不需要把序列的排序完整做完，平均只需線性時間即可找到結果，不過最差時間複雜度仍要

$O(n^2)$。

快速選擇(Quickselect)演算法，快速尋找第K小或是第K大的元素
Quick Sort 演算法原理與實作

Q7

• LXS

【題目】

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.

【做法】

使用三元樹，每次挑出出現頻率最低的三個符號，將三者的頻率總和作為新節點的頻率
對於任意三元樹 Leaf node數量 = Internal node數x2+1
對於節點數偶數加上頻率為0的dummy，使其在建構過程保持三元樹的性質

【Pseudocode】

def huffmanTernary(characters=c):
    if len(c) % 2 == 0:
        c += node(left=None, mid=None, right=None, freq=0)
    n=len(c)
    PQ = PriorityQueue(c)
    for i in range(1, n//2+1):
        u, v, w = PQ.extractMin(), PQ.extractMin(), PQ.extractMin()
        newNode = node(left=u, mid=v, right=w, freq=u.freq + v.freq + w.freq)
        PQ.insert(newNode)
    return PQ.extractMin()

Time complexity:

$O(nlogn)$

【證明】

Let

$C$ be a alphabet with frequency

$f(c_i)$ defined for each character

$c_i\in C$.

引理一 (Greedy-choice)

Let

$c_1,c_2,c_3$ be three characters in

$C$ with minimum frequencies. Then there exists an optimal prefix code for

$C$ in which the codewords for

$c_1,c_2,c_3$ have the same length and differ only in the last bit.

假設

$c_1,c_2,c_3$ 其中一個在上一層，將其調換編碼長度會更低

$$\begin{gathered} B(T)-B(T^{\prime }) \\ =\sum _{c\in C}f(c)d_T(c)-\sum _{c\in C}f(c)d_{T^{\prime }}(c) \\ =f(x)d_T(x)+f(c1)d_T(c1)-f(x)d_{T^{\prime }}(x)-f(c1)d_{T^{\prime }}(c1) \\ =f(x)d_T(x)+f(c1)d_T(c1)-f(x)d_T(c1)-f(c1)d_T(x) \\ =(f(x)-f(c1))(d_T(x)-d_T(c1)) \\ \ge 0 \end{gathered}$$
同理可證

$T^{\prime }$與

$T^{″}$，

$T^{″}$與

$T^{‴}$

引理二 (Optimal substructure)

Let

$c_1,c_2,c_3$ be three characters in C with minimum frequency. Let

$C^{\prime }$ =

$C\setminus \{c_1,c_2,c_3\}\cup c^{\prime }$. Define

$f$ for

$C^{\prime }$ as for

$C$, and

$f(c^{\prime })=f(c_1)+f(c_2)+f(c_3)$. Let

$T^{\prime }$ be any tree representing an optimal prefix code for the alphabet

$C^{\prime }$. Then the tree

$T$ , obtained from

$T^{\prime }$ by replacing the leaf node for

$c_3$ with an internal node having

$c_1,c_2,c_3$ as children, represents an optimal prefix code for the alphabet C.

$B(T^{\prime })=B(T)-f(c_1)-f(c_2)-f(c_3)$
假設

$T$不是最佳解，即存在一個

$T^{″}$，以致

$B(T^{″})<B(T)$，從引理一可得知

$B(T^{″})$中存在sebling關係的

$c_1,c_2,c_3$，如果我們將

$c_1,c_2,c_3$與其parent改為一節點

$p$，且

$f(p)=f(c_1)+f(c_2)+f(c_3)$，稱作

$T^{‴}$那麼

$\begin{array}{rl}B(T^{‴})& =B(T^{″})-f(c_1)-f(c_2)-f(c_3)\\ & <B(T)-f(c_1)-f(c_2)-f(c_3)& \text{Since B(T'')<B(T)}\\ & =B(T^{\prime })& \text{Equation in the first line}\end{array}$
此時發生矛盾，

$B(T^{‴})<B(T^{\prime })$即

$T^{\prime }$並非Optimal coding tree for

$C^{\prime }$，由此反證

$T$必為Optimal coding tree for

$C$。

由引理一與引理二可以得證我們得到的編碼樹是最佳解。

Q8

• LXS

【題目】

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

Character	Huffman code	frequency	depth/length
a	11	22	2
b	10100	2	5
c	0011	5	4
d	10101	3	5
e	010	5	3
f	100	8	3
g	011	7	3
h	00	11	2