PTT數位生活區 / Programming

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

看板Programming作者 (Terry)時間12年前 (2012/06/04 07:38), 編輯推噓1(1推 0噓 22→)
留言23則, 3人參與, 最新討論串5/8 (看更多)
※ 引述《sorryChen (陳揚和)》之銘言： : ※ 引述《sorryChen (陳揚和)》之銘言： : : 給定N個set, 規定至少個set, 使選的sets的集合包含的element個數越少越好 : 請原諒不太懂推文中所寫的所以舉例一下 : ex: S0={0}, S1={1}, S2={2},S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={1,3} : 假設都排好了 : M=4好了, 選S1,S2,S4,S5 : M=7好了, 選S1,S2,S3,S4,S5,S6,S7, 反正不選S0, 想說排序選前面的不見得最好 : ※ 發信站: 批踢踢實業坊(ptt.cc) : ◆ From: 207.151.93.115 : ※ 編輯: sorryChen 來自: 207.151.93.115 (06/01 12:24) : → Lordaeron:刪重覆後, s1~s7都為空, 有問題嗎? 210.59.250.101 06/01 12:59 : → sorryChen:不懂怎麼刪重複耶 刪調有幫助嗎? 108.94.138.88 06/01 15:39 : → sorryChen:若有重複過的element都刪去嗎,那若都刪 108.94.138.88 06/01 15:40 : → sorryChen:如何選擇 108.94.138.88 06/01 15:40 : → sorryChen:那要怎麼選擇呢 ? 108.94.138.88 06/01 15:41 init :S0={0}, S1={1}, S2={2},S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={1,3} 1.S0={0}, S1={}, S2={2},S3={3}, S4={,2}, S5={,2}, S6={2,3}, S7={,3} 2.S0={0}, S1={}, S2={},S3={3}, S4={,}, S5={,}, S6={,3}, S7={,3} 3.S0={0}, S1={}, S2={},S3={}, S4={,}, S5={,}, S6={,}, S7={,} so, S4={,}, S5={,}, S6={,}, S7={,} 為所選,因為被刪的element count 最大的 由 → stimim:選 4567 有 {1,2,3} 選 1245 只有 {1,2} 140.112.49.204 06/04 08:27 所講, 所以加上已知1,2 被刪4 次, 3. 被刪3 次. 這會不會比較好選? 有這麼多已知條件, 還需要指數時間來找嗎? 我不會證了. 請高人吧. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.162.12.97
→
06/04 08:27, , 1F
選 4567 有 {1,2,3} 選 1245 只有 {1,2}
06/04 08:27, 1F
→
06/04 10:25, , 2F
噢, 哪就選少的囉
06/04 10:25, 2F
→
06/04 10:29, , 3F
增增刪刪就化簡成聯集差集,就簡單了.
06/04 10:29, 3F
→
06/04 10:38, , 4F
你要用數學的方式表達,高興就好
06/04 10:38, 4F
→
06/04 11:44, , 5F
不是表達不表達,而是你這種算法黑手動作修來
06/04 11:44, 5F
→
06/04 11:45, , 6F
修去,不覺得很累嗎?其實就只是求差集而已.
06/04 11:45, 6F
→
06/04 12:07, , 7F
哦..沒辨法, 算法黑手就是這樣囉.
06/04 12:07, 7F
→
06/04 12:09, , 8F
你寫程式可以直接求集的就好囉
06/04 12:09, 8F
→
06/04 12:09, , 9F
我認為是把不同層次的東西混在一起,才變黑手
06/04 12:09, 9F
→
06/04 12:09, , 10F
求差集的
06/04 12:09, 10F
→
06/04 12:10, , 11F
但沒有人都是用直接求的啦,做資料結構不難.
06/04 12:10, 11F
→
06/04 12:14, , 12F
不難啊,等你囉.
06/04 12:14, 12F
→
06/04 12:14, , 13F
反正我是演算法黑手,跟你不同.
06/04 12:14, 13F
→
06/04 12:15, , 14F
你還是快推導一下,我的方法會不會有錯吧
06/04 12:15, 14F
推
06/10 06:48, , 15F
樓上,我已經回文指出你的方法有錯.
06/10 06:48, 15F
→
06/10 06:50, , 16F
我覺得當你不確定你自己很對,不要太自信滿滿
06/10 06:50, 16F
→
06/10 06:55, , 17F
樓下的, 自信滿滿的是你吧, 怎麼算到我
06/10 06:55, 17F
→
06/10 06:55, , 18F
身上來了.
06/10 06:55, 18F
→
06/10 06:58, , 19F
別人回過1245了,還要你特別發一篇?
06/10 06:58, 19F
※ 編輯: Lordaeron 來自: 1.162.1.146 (06/10 07:04) ※ 編輯: Lordaeron 來自: 1.162.1.146 (06/10 07:08)
→
06/10 07:12, , 20F
原po指明我回文中第一方法有錯,我已經承認.
06/10 07:12, 20F
→
06/10 07:12, , 21F
這樣說來,我是怎麼自信滿滿了?
06/10 07:12, 21F
→
06/10 07:13, , 22F
至於我文中第二方法,是老實將所有(N,M)組合
06/10 07:13, 22F
→
06/10 07:14, , 23F
拿出來找最少合併數,這是暴力法,當然有信心.
06/10 07:14, 23F
‣ 更多 Lordaeron 的文章
文章代碼(AID): #1Fo_M3zA (Programming)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 5 之 8 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共8篇)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Lordaeron 的文章
文章代碼(AID): #1Fo_M3zA (Programming)