PTT數位生活區 / Programming

算法問題 (從N個set選m個包含最少的元素)

看板Programming作者 (陳揚和)時間12年前 (2012/06/01 11:13), 編輯推噓5(5推 0噓 17→)
留言22則, 6人參與, 最新討論串1/8 (看更多)
給定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)
→
06/01 11:56, , 1F
是union 後的元素最少吧?
06/01 11:56, 1F
→
06/01 11:58, , 2F
先sort每個SET的element,再刪重覆(ALL)
06/01 11:58, 2F
→
06/01 11:59, , 3F
再sort SET by element number
06/01 11:59, 3F
→
06/01 11:59, , 4F
其中前M 個就是你要的.
06/01 11:59, 4F
→
06/01 12:00, , 5F
N sets 有n element,sort 用nlgn
06/01 12:00, 5F
→
06/01 12:01, , 6F
刪重覆, 用n^2,有N sets, 再sort
06/01 12:01, 6F
→
06/01 12:02, , 7F
用NlgN, 加一加, 不用polynomial time
06/01 12:02, 7F
→
06/01 14:38, , 8F
對有進行過刪重覆的才需要被第二次sort
06/01 14:38, 8F
→
06/01 15:42, , 9F
存一份copy沒問題但還是不懂您怎麼選擇
06/01 15:42, 9F
→
06/01 15:55, , 10F
或者,loop n elements 去count出各
06/01 15:55, 10F
→
06/01 15:56, , 11F
element 的個數. 再loop N sets, 去為它
06/01 15:56, 11F
→
06/01 15:57, , 12F
所包含的elements 的count 作相加. 取
06/01 15:57, 12F
→
06/01 15:57, , 13F
最大者.
06/01 15:57, 13F
推
06/03 19:35, , 14F
可以問一下N跟m可能有多大嗎?我猜很大啦XD
06/03 19:35, 14F
推
06/10 13:32, , 15F
好難 :( 本來想把 set cover problem 轉成
06/10 13:32, 15F
→
06/10 13:32, , 16F
這個問題,但是失敗了,沒辦法在P轉換 >"<
06/10 13:32, 16F
→
06/10 22:39, , 17F
這個問題不是被證明是NPC了嗎？
06/10 22:39, 17F
→
06/10 22:40, , 18F
喔，沒看清楚題目，搞錯了
06/10 22:40, 18F
推
06/12 20:42, , 19F
這個問題很類似在圖中找一段長度的路徑,使
06/12 20:42, 19F
→
06/12 20:43, , 20F
路徑權重最小.
06/12 20:43, 20F
推
06/12 20:46, , 21F
似乎不像P的問題
06/12 20:46, 21F
推
06/13 23:26, , 22F
不行... 還是想不到... orz
06/13 23:26, 22F
‣ 更多 sorryChen 的文章
文章代碼(AID): #1Fo3C-Iy (Programming)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 8 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共8篇)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 sorryChen 的文章
文章代碼(AID): #1Fo3C-Iy (Programming)