作者yauhh (喲)
看板Programming
標題Re: 算法問題 (從N個set選m個包含最少的元素)
時間Sun Jun 10 06:35:44 2012
※ 引述《Lordaeron (Terry)》之銘言：
: 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 最大的
這種解釋方法太恐怖. 你可能認為會,發生重覆而刪掉的位置,代表那些集合合併之後
增加總共元素的數目的機會會減低,所以最後你要挑刪掉的元素項目較多的集合,但是,
顯然是忽略了其他沒有重覆元素存在,然而並不會增加合併元素數目的集合.
例如:
S0={0}, S1={1], S2={2}, S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={3,4}
1.因為1有重覆所以刪掉全部的1:
S0={0}, S1={], S2={2}, S3={3}, S4={,2}, S5={,2}, S6={2,3}, S7={3,4}
2.因為2有重覆所以刪掉全部的2:
S0={0}, S1={], S2={}, S3={3}, S4={,}, S5={,}, S6={,3}, S7={3,4}
3.因為3有重覆所以刪掉全部的3:
S0={0}, S1={], S2={}, S3={}, S4={,}, S5={,}, S6={,}, S7={,4}
4.已經沒有重覆了所以依照被刪掉的元素數目,由大到小排序:
S4={,}, S5={,}, S6={,}, S7={,4}, S1={], S2={}, S3={}, S0={0}
5.因為指定要的M sets, M數目為4,所以取前四個sets:
S4 U S5 U S6 U S7 = {1,2,3,4}
S4 U S5 U S6 U S7 是你所提刪除方式的結果,雖然它是原po所言 "數目越少越好"
的潛在解之一, 但是這個情況,是 S1 U S2 U S4 U S5 = {1,2} 答案比較好.
而且你的方法所找出來的解,不但品質差,而且相當差.
實作上很難實作,答案是否適當也要看情況,而且也沒有相當的道理讓人相信
這演算法是對的.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.227.2
※ 編輯: yauhh 來自: 59.112.227.2 (06/10 06:53)
1F：→ Lordaeron:所以,你求出最佳解的做法是? 1.162.1.146 06/10 06:56
2F：→ Lordaeron:再說, 1245的問題, 已經有人回了 1.162.1.146 06/10 06:57
3F：→ Lordaeron:應該不用你發一篇文章來講,因為你還是 1.162.1.146 06/10 06:57
4F：→ Lordaeron:後知後覺的哪位. 1.162.1.146 06/10 06:57
5F：→ yauhh:我求不錯的解的做法,在我前文中第二方法中. 59.112.227.2 06/10 07:04
6F：→ yauhh:至於所謂後知後覺,其實是不知不覺,因為我根 59.112.227.2 06/10 07:05
7F：→ yauhh:本沒想要破解你的方法,是從理解你的方法之後 59.112.227.2 06/10 07:05
8F：→ yauhh:看出漏餡之處. 59.112.227.2 06/10 07:05
9F：→ Lordaeron:別人已經講過了. 你是沒看別人的回文? 1.162.1.146 06/10 07:06
10F：→ Lordaeron:何苦去將他人的話轉述一次當作自己的呢 1.162.1.146 06/10 07:07
11F：→ yauhh:那又怎麼樣?最起碼我發表了自己的破解解釋. 59.112.227.2 06/10 07:07
12F：→ Lordaeron:對了,你還未證明你的做法是P, 不是NP 1.162.1.146 06/10 07:07
13F：→ Lordaeron:要當算法高手, 還要證明哦. 1.162.1.146 06/10 07:07
14F：→ yauhh:我不需要證明方法是NP,因為並沒有討論這一點 59.112.227.2 06/10 07:08
15F：→ yauhh:你說我說的是別人講過的事情,對,因為在本文 59.112.227.2 06/10 07:15
16F：→ yauhh:張貼之前,我根本看不懂你的方法究竟怎麼做. 59.112.227.2 06/10 07:15
17F：→ yauhh:你描述的時候前後說詞修來修去,黑手動作多, 59.112.227.2 06/10 07:16
18F：→ yauhh:是到前一位bob板友質疑才看明白你所講的. 59.112.227.2 06/10 07:17
19F：→ Lordaeron:你看不懂沒關係,有別人看出問題了 1.162.1.146 06/10 07:17
20F：→ yauhh:可見你講了這個方法有多難懂. 59.112.227.2 06/10 07:18
21F：→ Lordaeron:你不知不覺而已,再說是不是NP才是發 1.162.1.146 06/10 07:18
22F：→ Lordaeron:問者的重點,你連別人問什麼都不知,回 1.162.1.146 06/10 07:18
23F：→ yauhh:講方法講的別人不懂,這也是演算學者的大忌. 59.112.227.2 06/10 07:18
24F：→ Lordaeron:得比我還要爽, 實在是佩服. 1.162.1.146 06/10 07:19
25F：→ yauhh:少來一套,你也沒有解釋你的方法是不是NP. 59.112.227.2 06/10 07:19
26F：→ yauhh:為什麼我突然要回答方法是不是NP? 59.112.227.2 06/10 07:20
27F：→ Lordaeron:哈....你真的是一個不看文的人.....不行 1.162.1.146 06/10 07:20
28F：→ Lordaeron:不看文而回文,是回文的大忌 1.162.1.146 06/10 07:20
29F：→ yauhh:你是說你推文中說你方法是P那樣子嗎?但是, 59.112.227.2 06/10 07:20
30F：→ Lordaeron:請回去看原po 的問題, 謝謝囉. 1.162.1.146 06/10 07:20
31F：→ yauhh:你的方法錯,所以P或NP,沒用,不是嗎? 59.112.227.2 06/10 07:21
32F：→ yauhh:那你到底要不要承認你犯了錯? 59.112.227.2 06/10 07:21
33F：→ Lordaeron:不要但是了, 不看問題而回文, 也是 1.162.1.146 06/10 07:21
你在講什麼? 你說你的推文重要到值得看嗎?
抱歉,我只看原po的問題. 至於你自己製造的問題,請自己收拾.
34F：→ yauhh:如果不要承認,那就不要囉唆囉,我還接到水球 59.112.227.2 06/10 07:21
35F：→ Lordaeron:演算學者的大忌. 1.162.1.146 06/10 07:22
36F：→ yauhh:要我加油,我就不知道是要加什麼油 59.112.227.2 06/10 07:22
※ 編輯: yauhh 來自: 59.112.227.2 (06/10 07:23)
37F：→ Lordaeron:錯什麼? 我從沒說過我對過 1.162.1.146 06/10 07:22
38F：→ Lordaeron:你真的要加油, 連原po 在問什麼都不知 1.162.1.146 06/10 07:23
39F：→ Lordaeron:就回文了, 嗯演算學者的大忌. 1.162.1.146 06/10 07:23
40F：→ Lordaeron:但還好, 我不是演算學者. 1.162.1.146 06/10 07:23
41F：→ yauhh:你連推同一組推文二次,有什麼意義? 59.112.227.2 06/10 07:24
42F：→ yauhh:我也不是演算學者啊 59.112.227.2 06/10 07:24
43F：→ Lordaeron:原po 就在問這是不是NP 問題了,大哥 1.162.1.146 06/10 07:24
44F：→ yauhh:他是問這問題是不是NP,而不是解法是不是NP. 59.112.227.2 06/10 07:25
45F：→ Lordaeron:哇, 還有問題跟解法分離的說法? 1.162.1.146 06/10 07:25
46F：→ Lordaeron:記住, 我是黑手, 不是學者, 沒大忌.沒差 1.162.1.146 06/10 07:26
47F：→ yauhh:你第一篇回文只說像是P 59.112.227.2 06/10 07:26
48F：→ yauhh:說錯了,你第一篇推文只說是P. 59.112.227.2 06/10 07:26
49F：→ yauhh:所以你就是說,方法被抓到錯,不當一回事. 59.112.227.2 06/10 07:27
50F：→ Lordaeron:是啊, 我推導如推文所述 1.162.1.146 06/10 07:27
51F：→ yauhh:第二篇推文,你沒有提到P or NP. 59.112.227.2 06/10 07:27
52F：→ yauhh:第三篇推文是我和原po的對話. 59.112.227.2 06/10 07:27
53F：→ Lordaeron:不當一回事,有人連 1.162.1.146 06/10 07:28
54F：→ Lordaeron:"問題是不是NP,而不是解法是不是NP"都跑 1.162.1.146 06/10 07:28
55F：→ yauhh:第五篇推文,你根本沒有提P or NP. 59.112.227.2 06/10 07:28
56F：→ Lordaeron:出來了. 再說, 我是黑手, 不是學者 1.162.1.146 06/10 07:28
57F：→ yauhh:第六篇bob板友提問,你用回文方式處理,但是, 59.112.227.2 06/10 07:28
58F：→ yauhh:但是你那篇回文雖然回了,但是解答中看得出 59.112.227.2 06/10 07:29
59F：→ Lordaeron:不用但是了. 你的問題NP,解不NP, 我輸了 1.162.1.146 06/10 07:29
60F：→ yauhh:漏餡漏很多. 自刪了. 59.112.227.2 06/10 07:29
61F：→ Lordaeron:你繼續吧, 我們讀的書不同,沒什麼好講的 1.162.1.146 06/10 07:30
62F：→ yauhh:至於現在你一直在說我不看人家的文,但是我 59.112.227.2 06/10 07:30
63F：→ Lordaeron:加油. 1.162.1.146 06/10 07:30
64F：→ yauhh:核對發現我都有看啊. 你的確沒有討論P or NP 59.112.227.2 06/10 07:30
65F：→ yauhh:那你說說這個問題是不是NP? 59.112.227.2 06/10 07:31
66F：→ yauhh:咦,我都已經這樣很有誠意跟你核對文章內容.. 59.112.227.2 06/10 07:33
67F：→ Lordaeron:問題NP or not, 解法NP or not, 想請問 1.162.1.146 06/10 07:33
68F：→ yauhh:你到底在哪裏做了"是否為NP"的討論? 59.112.227.2 06/10 07:33
69F：→ Lordaeron:出自何書之說, 讓我拜讀一下吧. 1.162.1.146 06/10 07:34
不好意思,不屑分享. 因為到此我感覺你很沒有誠意.
70F：→ yauhh:我承認我並沒有討論NP. 那你說我該討論NP, 59.112.227.2 06/10 07:34
71F：→ yauhh:為什麼你不討論呢? 59.112.227.2 06/10 07:34
※ 編輯: yauhh 來自: 59.112.227.2 (06/10 07:35)
72F：→ Lordaeron:不屑分享. 因為到此我感覺你很沒有誠意. 1.162.1.146 06/10 07:36
73F：→ Lordaeron:哈.............. 1.162.1.146 06/10 07:36
74F：→ yauhh:如果你不是心虛,不會這樣纏著我的推文不放. 59.112.227.2 06/10 07:37
75F：→ yauhh:那我離開programming板囉,星期天要輕鬆,bye 59.112.227.2 06/10 07:38
76F：→ Lordaeron:見鬼呢,連po問什麼都沒看就回文的人, 還 1.162.1.146 06/10 07:40
77F：→ Lordaeron:可以說別人心虛,實在是佩服. 1.162.1.146 06/10 07:41
78F：→ Lordaeron:這倒底是誰在鬧呢, hohoho.. 1.162.1.146 06/10 07:42
79F：推 sorryChen:實在不好意思, 讓兩位兄台替我費心了 108.94.138.88 06/11 15:21
80F：→ Lordaeron:我的看法, 不是NP problem 210.59.250.101 06/11 16:21
81F：→ Lordaeron:你去理哪個問題NP解NP 的幹嘛呢. 210.59.250.101 06/11 16:21
82F：→ yauhh:可是是你自己去強調是否NP的,這會兒突然變 59.112.231.99 07/01 19:43
83F：→ yauhh:別人去理NP不NP. 至於原po既然問了NP不NP, 59.112.231.99 07/01 19:44
84F：→ yauhh:你又要後來否定原po的問題,你很矛盾耶. 59.112.231.99 07/01 19:44