PageRank



轉移公告

計劃把 http://blog.hoamon.info/ 文章全部轉移至 http://www.hoamon.info/blog/ 這裡,而本 Blogger 站台的文章近 500 篇,我預計在 2014-12-31 前移轉完畢,完成後 http://blog.hoamon.info/ 將只作代轉服務,一律把舊連結如 http://blog.hoamon.info/index.html 轉成 http://www.hoamon.info/blog/index.html ,敬請舊雨新知互相走告。

新文章只發佈在 http://www.hoamon.info/blog/

何岳峰 敬上

2011年1月23日 星期日

道路施工的排程問題,類似背包問題,但須考慮不同的排列方式

如:長度 10 公尺的路面,若有 7 公尺/日、 5 公尺/日、 3 公尺/日的施工工班可供選擇,則有幾種的排程組合? 此問題很像背包問題,但在背包問題中,它不須考慮裝入物品的順序,而只考慮種類。若問題改為路面總長度 1000 公尺,而有 [260, 230, 190, 140, 80] 幾種工班時,我的解答是 69225 種。以下是我的解法:

 1 class LineSerial:
 2     u"""  目的:解路面排程問題,如:長度 10 公尺的路面,若有 7 公尺/日、 5 公尺/日、 3 公尺/日
 3         的施工工班可供選擇,則有幾種的排程組合。
 4
 5         解如下,共 17 種:
 6             [7, 7], [7, 5], [7, 3],
 7             [5, 7], [5, 5],
 8             [5, 3, 7], [5, 3, 5], [5, 3, 3],
 9             [3, 7],
10             [3, 5, 7], [3, 5, 5], [3, 5, 3],
11             [3, 3, 7], [3, 3, 5],
12             [3, 3, 3, 7], [3, 3, 3, 5], [3, 3, 3, 3],
13     """
14     def __init__(self, total, sizes):
15         """ serial_times 則是在計算 serial 函式被呼叫幾次。
16         """
17         sizes.sort(reverse=True)
18         self._sizes = sizes
19         self.serial_times = 0
20         self.result = []
21         self.serial(total, None, [])
22
23
24     def serial(self, total, length, tmp):
25         u""" 將 total 依序給 _sizes 中的所有元素去切,切完後就放入 tmp ,
26             當 total <= 0 時, 再放入 self.result 中。
27         """
28         #self.serial_times += 1
29         tmp.append(length)
30         if total <= 0:
31             self.result.append(tmp[1:])
32             return
33
34         for s in self._sizes: self.serial(total-s, s, tmp[:])
35
36
37
38 if __name__ == '__main__':
39     from time import time
40     total = 1000
41     lengths = [260, 230, 190, 140, 80]
42     time0 = time()
43     cs = LineSerial(total, lengths)
44     print time() - time0
45     print u'總組合數: %s' % len(cs.result)
46     print u'serial 遞迴次數: %s' % cs.serial_times
47     #for i in cs.result: print i

沒有留言:

張貼留言

注意:只有此網誌的成員可以留言。

Related Posts Plugin for WordPress, Blogger...