※ 引述《Iriss (好害羞的愛情故事)》之銘言：
: ※ 引述《sophialiege ()》之銘言：
: : 只有一個水龍頭很容易, 如果有兩個水龍頭可以排成兩隊呢?
: : 解:
: : 先排一隊 (sort ni in non-decreasing order)
: : 哪一水龍頭空了就讓最前面一個上
: : n個水龍頭也適用
: 既然我回了是 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 4 3 total = 16
我發現我看錯了，這題問的是等待時間和...
不過我舉的例子依然可以用
Greedy algorithm gives waiting time 0 + 0 + 9 + 10 + 14 = 33
Optimal waiting time is 0 + 0 +10 + 9 + 13 = 32
不過是不是 NP-hard 還要再想想。
--
迴旋如藤－
蔓 波動的溫柔拂飛柳絮
淡妝
散、漫、在西施採菱的湖邊
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 68.181.255.120
→
03/28 16:19, , 1F
03/28 16:19, 1F
討論串 (同標題文章)