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

[Lordaeron (Terry)]

※ 引述《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
→ stimim:選 4567 有 {1,2,3} 選 1245 只有 {1,2}
→ Lordaeron:噢, 哪就選少的囉
→ yauhh:增增刪刪就化簡成聯集差集,就簡單了.
→ Lordaeron:你要用數學的方式表達,高興就好
→ yauhh:不是表達不表達,而是你這種算法黑手動作修來
→ yauhh:修去,不覺得很累嗎?其實就只是求差集而已.
→ Lordaeron:哦..沒辨法, 算法黑手就是這樣囉.
→ Lordaeron:你寫程式可以直接求集的就好囉
→ yauhh:我認為是把不同層次的東西混在一起,才變黑手
→ Lordaeron:求差集的
→ yauhh:但沒有人都是用直接求的啦,做資料結構不難.
→ Lordaeron:不難啊,等你囉.
→ Lordaeron:反正我是演算法黑手,跟你不同.
→ Lordaeron:你還是快推導一下,我的方法會不會有錯吧
推 yauhh:樓上,我已經回文指出你的方法有錯.
→ yauhh:我覺得當你不確定你自己很對,不要太自信滿滿
→ Lordaeron:樓下的, 自信滿滿的是你吧, 怎麼算到我
→ Lordaeron:身上來了.
→ Lordaeron:別人回過1245了,還要你特別發一篇?
※ 編輯: Lordaeron       來自: 1.162.1.146          (06/10 07:04)
※ 編輯: Lordaeron       來自: 1.162.1.146          (06/10 07:08)
→ yauhh:原po指明我回文中第一方法有錯,我已經承認.
→ yauhh:這樣說來,我是怎麼自信滿滿了?
→ yauhh:至於我文中第二方法,是老實將所有(N,M)組合
→ yauhh:拿出來找最少合併數,這是暴力法,當然有信心.