作者sorryChen (陳揚和)
看板Programming
標題算法問題
時間Fri Jun 1 11:13:00 2012
給定N個set, 規定至少選其中M個set, 使選的sets的集合包含的element個數越少越好
舉例說明,一個往返兩地的包車要服務N個客戶中的至少M位,
每位客戶有要搭車的日期表, 比如乘客一, 1,3,5, 乘客二, 1,2,3, 乘客三 1,15,30...等
包車希望在服務M位乘客的情況下發車日越少越好...需要寫個程式來選乘客...
這難道會是一個NP Complete的問題嗎?
和Set Cover或類似註明的NP-Complete應該不同吧
有沒有高手能解惑
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 207.151.93.115
※ 編輯: sorryChen 來自: 207.151.93.115 (06/01 11:13)
1F：→ Lordaeron:是union 後的元素最少吧? 210.59.250.101 06/01 11:56
2F：→ Lordaeron:先sort每個SET的element,再刪重覆(ALL) 210.59.250.101 06/01 11:58
3F：→ Lordaeron:再sort SET by element number 210.59.250.101 06/01 11:59
4F：→ Lordaeron:其中前M 個就是你要的. 210.59.250.101 06/01 11:59
5F：→ Lordaeron:N sets 有n element,sort 用nlgn 210.59.250.101 06/01 12:00
6F：→ Lordaeron:刪重覆, 用n^2,有N sets, 再sort 210.59.250.101 06/01 12:01
7F：→ Lordaeron:用NlgN, 加一加, 不用polynomial time 210.59.250.101 06/01 12:02
8F：→ Lordaeron:對有進行過刪重覆的才需要被第二次sort 210.59.250.101 06/01 14:38
9F：→ sorryChen:存一份copy沒問題但還是不懂您怎麼選擇 108.94.138.88 06/01 15:42
10F：→ Lordaeron:或者,loop n elements 去count出各 210.59.250.101 06/01 15:55
11F：→ Lordaeron:element 的個數. 再loop N sets, 去為它 210.59.250.101 06/01 15:56
12F：→ Lordaeron:所包含的elements 的count 作相加. 取 210.59.250.101 06/01 15:57
13F：→ Lordaeron:最大者. 210.59.250.101 06/01 15:57
14F：推 yoco315:可以問一下N跟m可能有多大嗎?我猜很大啦XD182.235.170.158 06/03 19:35
15F：推 yoco315:好難 :( 本來想把 set cover problem 轉成182.235.170.158 06/10 13:32
16F：→ yoco315:這個問題,但是失敗了,沒辦法在P轉換 >"<182.235.170.158 06/10 13:32
17F：→ neverfly:這個問題不是被證明是NPC了嗎？ 114.32.224.229 06/10 22:39
18F：→ neverfly:喔，沒看清楚題目，搞錯了 114.32.224.229 06/10 22:40
19F：推 yauhh:這個問題很類似在圖中找一段長度的路徑,使 61.231.64.224 06/12 20:42
20F：→ yauhh:路徑權重最小. 61.231.64.224 06/12 20:43
21F：推 Arton0306:似乎不像P的問題 114.42.50.185 06/12 20:46
22F：推 yoco315:不行... 還是想不到... orz 111.185.67.169 06/13 23:26