# 演算法作業七

###### tags: `演算法`

1. Show how to use property 2 of Lemma 16.12 to determine in time O(|A|) whether or not a given set A of tasks is independent.

Answer:

    Independent(d[],n){
        N[1..n]={0}
        for i=1:n
            if d[i]<=i
                N[d[i]]+=1
        for t=1:n
            N[t]+=N[t-1]
            if N[t]>t
                return false
        return true
    }
    

2. Suppose you are given a set S = { $a_1, a_2, ... , a_n$ } of tasks, where task $a_i$ requires $p_i$ units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let $c_i$ be the completion time of task $a_i$, that is, the time at which task $a_i$ completes processing. Your goal is to minimize the average completion time, that is, to minimize . Give an algorithm that schedules the tasks so as to minimize the average completion time. Each task must run non-preemptively, that is, once task $a_i$ starts, it must run continuously for pi units of time. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

Answer:
我們知道每個task實際完成的時間點$c_i$會等於自己的時間$p_i$加上所有在它之前完成的task的時間和也就是$\underbrace{\sum}_{0\le j \le i-1}p_j$
所以$c_i=p_i+\underbrace{\sum}_{0\le j \le i-1}p_j$
所以$\underbrace{\sum}_{0\le i \le n}c_i=\underbrace{\sum}_{0\le i \le n}(p_i+\underbrace{\sum}_{0\le j \le i-1}p_j)$
所以我們的目標就是要minimize $\underbrace{\sum}_{0\le i \le n} \underbrace{\sum}_{0 \le j \le i-1}p_j$
要做到這件事我們就希望processing time愈長的工作排在愈後面，因為可以發現排在越前面的工作時間會被加越多次，所以越前面的工作processing time要越短
所以我們只要將S當中的工作依照processing time進行non decreasing order排列就可以
使用merge sort進行排列，時間複雜度是$O(nlog(n))$

    Schedule(S[],n){
        let p[1...n] be a new array
        for i=1:n
            p[i]=S[i].p //將活動的processing time放入
        MergeSort(p[],1,n)
        return p[]
    }

3. Suppose you have one machine and a set of n jobs $a_1, a_2, … , a_n$ to process on that machine. Each job $a_j$ has a processing time $t_j$, the same profit 1, and a deadline $d_j$. The machine can process only one job at a time, and job $a_j$ must run uninterruptedly for $t_j$ consecutive time units. If job $a_j$ is completed by its deadline $d_j$, you receive a unit profit, but if it is completed after its deadline, you receive a profit of 0. Give an algorithm to find the schedule that obtains the maximum amount of profit.

Answer:
此題可以看為01背包的變形
M[i][j]代表在的1~i的活動當中得到profit j的最少總活動時間

假設活動都以d[]升序排序好了
時間複雜度是$O(n^2)$

**初值:** $M[0][j]=Inf,M[i][0]=0,M[0][0]=0$
**遞迴式:** $M[i][j]=\begin{cases}
min(M[i-1][j],M[i-1][j-1]+t[i]) \ if \ M[i-1][j-1]+t[i]\le d[i]\\
M[i-1][j]\\
\end{cases}$
**解答:** 最短processing time:$M[n][j],\ max(M[n][j] \ and\ M[n][j]!=Inf)$、最好排程使用DFS找出並存在一個$S[]$ vector或array中
**pseudo code:**

    Function(t[],d[],n){
        let M[0..n][0..n] be new array
        M[0][0]=0
        for i=0:n
            M[0][i]=INF
            M[i][0]=INF
        for i=1:n
            for j=1:n
                if M[i-1][j-1]+t[i]<=d[i]
                    M[i][j]=min(M[i-1][j],M[i-1][j-1]+t[i])
                else
                    M[i][j]=M[i-1][j]
        max=M[n][0],max_j
        for i=1:n
            if M[n][i]==INF
                break
            if M[n][i]>max
                max=M[n][i]
                max_j=i
        
        let S[] be a new vector
        Schedule(S[],M[][],n,max_j)
        return S[]
    }
    Schedule(S[],M[],i,j){
        if i==0 or j==0
            return
        if M[i][j]==M[i-1][j-1]+t[i]
            Schedule(S[],M[],i-1,j-1)
            S.push_back(i)
        else
            Schedule(S[],M[],i,j-1)
    }