一道算法題随筆（2）

題目：一個公司下面有N個部門，現在要給每個部門配置設定任務，配置設定任務隻能按照配置設定的順序進行，不能同時配置設定兩個任務，隻能一個接一個的配置設定，但是配置設定完任務後，該部門可以立刻執行(不間斷)。配置設定一個任務的時間是a，執行的時間是b。你需要做的就是決定配置設定給每一個部門任務的順序，使得所有部門完成任務的總時間最短。

輸入樣例：

3                 （代表3個部門）

2  2

3  4

1  5               （第一組資料，前面為配置設定時間，後面為執行時間）

2  4

4  2

3  3                （第二組資料）

Case 1：8

Case 2: 11

分析：由于這道題資料量不會很大可以采用暴力破解法（這是一個萬能法），首先我們需要得到部門執行順序的全排列組合，然後過濾出排列組合長度等于部門數的組合，在計算出每一種排列所需的執行總時間，最後計算出執行時間最短的那種組合。

代碼：

# 建立同值清單
def create_list(list):
    ll = []
    for i in list:
        ll.append(i)
    return ll
# 往清單中插入一個資料的所有可能插入方法，這裡要注意的是python和其他語言的不同之處，清單的直接賦
# 值操作位址空間不變，是以寫了一個建立同值清單函數（很low，網上有很多種清單指派建立位址的方式，這
# 裡我就不改了）
def insert_k(list,k):
    if k not in list:
        result = [list]
        for i in range(len(list)+1):
            ll = create_list(list)
            ll.insert(i, k)
            result.append(ll)
    else:
        result = [list]
    return result

# 一個過濾掉全排列後長度不等于部門數的排列的裝飾器
def filter_len(fun):
    def wapper(li):
        result = fun(li)
        re = []
        for l in result:
            if len(l) == len(li):
                re.append(l)
        return re
    return wapper

# 帶過濾排列裝飾器的全排列函數
@filter_len
def permutations(li):
    result = []
    for i in li:
        result.append([i])
    for i in li:
        ll = create_list(result)
        for l in ll:
            re = insert_k(l, i)
            # print(re)
            for r in re:
                if r not in result:
                    result.append(r)
    return result

# 計算每一種排列所需的最終時長
def all_time(task_order):
    l = 0
    r = 0
    for index,task in enumerate(task_order):
        if index+1 <= len(task_order)-1:
            l += task.ready_time
            next_task_time = task_order[index+1].ready_time + task_order[index+1].do_time
            if next_task_time+l > l+task.do_time:
                r = next_task_time+l
            else:
                r = l+task.do_time
    return r

# 任務的類，ready_time 任務的準備時長，do_time任務的執行時長，no_dept部門id
class task_time(object):
    def __init__(self,ready_time,do_time,no_dept):
        self.ready_time = ready_time
        self.do_time = do_time
        self.no_dept = no_dept

# 主函數，計算最小時長的那種排列，并輸出最小時長和部門執行順序
if __name__=='__main__':
    dept_num = input('部門數：')
    task_list = []
    max_time = 0
    for i in range(dept_num):
        ready_time = input('第%sth部門的配置設定時長：'%i)
        do_time = input('第%sth部門的執行時長：'%i)
        task_list.append(task_time(ready_time,do_time,i))
        max_time += ready_time + do_time
    task_permutations = permutations(task_list)
    min_time = (max_time,)
    for task_order in task_permutations:
         l = all_time(task_order)
         # print(l)
         if l < min_time[0]:
             min_time = (l,task_order)
         else:
             continue
    print(min_time[0],'部門順序：',min_time[1][0].no_dept,min_time[1][1].no_dept,min_time[1][2].no_dept)