算法問題

[sorryChen (陳揚和)]

給定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)
→ Lordaeron:是union 後的元素最少吧?
→ Lordaeron:先sort每個SET的element,再刪重覆(ALL)
→ Lordaeron:再sort SET by element number
→ Lordaeron:其中前M 個就是你要的.
→ Lordaeron:N sets 有n element,sort 用nlgn
→ Lordaeron:刪重覆, 用n^2,有N sets, 再sort
→ Lordaeron:用NlgN, 加一加, 不用polynomial time
→ Lordaeron:對有進行過刪重覆的才需要被第二次sort
→ sorryChen:存一份copy沒問題但還是不懂您怎麼選擇
→ Lordaeron:或者,loop n elements 去count出各
→ Lordaeron:element 的個數. 再loop N sets, 去為它
→ Lordaeron:所包含的elements 的count 作相加. 取
→ Lordaeron:最大者.
推 yoco315:可以問一下N跟m可能有多大嗎?我猜很大啦XD
推 yoco315:好難 :( 本來想把 set cover problem 轉成
→ yoco315:這個問題,但是失敗了,沒辦法在P轉換 >"<
→ neverfly:這個問題不是被證明是NPC了嗎？
→ neverfly:喔，沒看清楚題目，搞錯了
推 yauhh:這個問題很類似在圖中找一段長度的路徑,使
→ yauhh:路徑權重最小.
推 Arton0306:似乎不像P的問題
推 yoco315:不行... 還是想不到... orz