作者Lordaeron (Terry)
站內Programming
標題Re: 算法問題 (從N個set選m個包含最少的元素)
時間Mon Jun 4 07:38:40 2012
※ 引述《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
1F：→ stimim:選 4567 有 {1,2,3} 選 1245 只有 {1,2} 140.112.49.204 06/04 08:27
2F：→ Lordaeron:噢, 哪就選少的囉 210.59.250.101 06/04 10:25
3F：→ yauhh:增增刪刪就化簡成聯集差集,就簡單了.218.160.110.179 06/04 10:29
4F：→ Lordaeron:你要用數學的方式表達,高興就好 210.59.250.101 06/04 10:38
5F：→ yauhh:不是表達不表達,而是你這種算法黑手動作修來218.160.110.179 06/04 11:44
6F：→ yauhh:修去,不覺得很累嗎?其實就只是求差集而已.218.160.110.179 06/04 11:45
7F：→ Lordaeron:哦..沒辨法, 算法黑手就是這樣囉. 210.59.250.101 06/04 12:07
8F：→ Lordaeron:你寫程式可以直接求集的就好囉 210.59.250.101 06/04 12:09
9F：→ yauhh:我認為是把不同層次的東西混在一起,才變黑手218.160.110.179 06/04 12:09
10F：→ Lordaeron:求差集的 210.59.250.101 06/04 12:09
11F：→ yauhh:但沒有人都是用直接求的啦,做資料結構不難.218.160.110.179 06/04 12:10
12F：→ Lordaeron:不難啊,等你囉. 210.59.250.101 06/04 12:14
13F：→ Lordaeron:反正我是演算法黑手,跟你不同. 210.59.250.101 06/04 12:14
14F：→ Lordaeron:你還是快推導一下,我的方法會不會有錯吧 210.59.250.101 06/04 12:15
15F：推 yauhh:樓上,我已經回文指出你的方法有錯. 59.112.227.2 06/10 06:48
16F：→ yauhh:我覺得當你不確定你自己很對,不要太自信滿滿 59.112.227.2 06/10 06:50
17F：→ Lordaeron:樓下的, 自信滿滿的是你吧, 怎麼算到我 1.162.1.146 06/10 06:55
18F：→ Lordaeron:身上來了. 1.162.1.146 06/10 06:55
19F：→ Lordaeron:別人回過1245了,還要你特別發一篇? 1.162.1.146 06/10 06:58
※ 編輯: Lordaeron 來自: 1.162.1.146 (06/10 07:04)
※ 編輯: Lordaeron 來自: 1.162.1.146 (06/10 07:08)
20F：→ yauhh:原po指明我回文中第一方法有錯,我已經承認. 59.112.227.2 06/10 07:12
21F：→ yauhh:這樣說來,我是怎麼自信滿滿了? 59.112.227.2 06/10 07:12
22F：→ yauhh:至於我文中第二方法,是老實將所有(N,M)組合 59.112.227.2 06/10 07:13
23F：→ yauhh:拿出來找最少合併數,這是暴力法,當然有信心. 59.112.227.2 06/10 07:14