看板 [ ACMCLUB ]
討論串[閒聊] 水龍頭
共 9 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
2
下一頁
尾頁
#9
Re: [閒聊] 水龍頭
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者jjchen.時間20年前 (2006/03/28 19:30), 編輯資訊
0
0
0
內容預覽:
我印象中是可以用matching做到, 可是要查一下怎麼做 ^_^. It should be in P, too.. --. ※ 發信站: 批踢踢兔(ptt2.cc). ◆ From: 140.112.28.117.
#8
Re: [閒聊] 水龍頭
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者jjchen.時間20年前 (2006/03/28 16:30), 編輯資訊
0
0
0
內容預覽:
這個問題和Minimum Average Completion Time等價 (\sum C_j) in scheduling. P||\sum C_j. 可以採用shortest-job-first schedule 得到optimal. This is a very special case f
#7
Re: [閒聊] 水龍頭
推噓0(0推 0噓 1→)留言1則，0人參與, 最新作者Iriss.時間20年前 (2006/03/28 16:30), 編輯資訊
0
0
0
內容預覽:
我發現我看錯了，這題問的是等待時間和.... 不過我舉的例子依然可以用. Greedy algorithm gives waiting time 0 + 0 + 9 + 10 + 14 = 33. Optimal waiting time is 0 + 0 +10 + 9 + 13 = 32. 不過
#6
Re: [閒聊] 水龍頭
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者Iriss.時間20年前 (2006/03/28 16:30), 編輯資訊
0
0
0
內容預覽:
既然我回了是 NP-hard，那只好來想一個反例. 假設五個人. 先排序 10, 9, 5, 4, 3. Greedy algorithm will give. 1. 10 4. 2. 9 5 3 total = 17. But optimal schedule is. 1. 10 5. 2. 9
#5
Re: [閒聊] 水龍頭
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者Iriss.時間20年前 (2006/03/28 16:00), 編輯資訊
0
0
1
內容預覽:
It's NP hard.. The proof is here:. http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec03.pdf. (這是我上學期的期末考題). --. 迴旋如藤－. 蔓 波動的溫柔拂飛柳絮.
首頁
上一頁
1
2
下一頁
尾頁