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

[yauhh (喲)]

※ 引述《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)
→ Lordaeron:所以,你求出最佳解的做法是?
→ Lordaeron:再說, 1245的問題, 已經有人回了
→ Lordaeron:應該不用你發一篇文章來講,因為你還是
→ Lordaeron:後知後覺的哪位.
→ yauhh:我求不錯的解的做法,在我前文中第二方法中.
→ yauhh:至於所謂後知後覺,其實是不知不覺,因為我根
→ yauhh:本沒想要破解你的方法,是從理解你的方法之後
→ yauhh:看出漏餡之處.
→ Lordaeron:別人已經講過了. 你是沒看別人的回文?
→ Lordaeron:何苦去將他人的話轉述一次當作自己的呢
→ yauhh:那又怎麼樣?最起碼我發表了自己的破解解釋.
→ Lordaeron:對了,你還未證明你的做法是P, 不是NP
→ Lordaeron:要當算法高手, 還要證明哦.
→ yauhh:我不需要證明方法是NP,因為並沒有討論這一點
→ yauhh:你說我說的是別人講過的事情,對,因為在本文
→ yauhh:張貼之前,我根本看不懂你的方法究竟怎麼做.
→ yauhh:你描述的時候前後說詞修來修去,黑手動作多,
→ yauhh:是到前一位bob板友質疑才看明白你所講的.
→ Lordaeron:你看不懂沒關係,有別人看出問題了
→ yauhh:可見你講了這個方法有多難懂.
→ Lordaeron:你不知不覺而已,再說是不是NP才是發
→ Lordaeron:問者的重點,你連別人問什麼都不知,回
→ yauhh:講方法講的別人不懂,這也是演算學者的大忌.
→ Lordaeron:得比我還要爽, 實在是佩服.
→ yauhh:少來一套,你也沒有解釋你的方法是不是NP.
→ yauhh:為什麼我突然要回答方法是不是NP?
→ Lordaeron:哈....你真的是一個不看文的人.....不行
→ Lordaeron:不看文而回文,是回文的大忌
→ yauhh:你是說你推文中說你方法是P那樣子嗎?但是,
→ Lordaeron:請回去看原po 的問題, 謝謝囉.
→ yauhh:你的方法錯,所以P或NP,沒用,不是嗎?
→ yauhh:那你到底要不要承認你犯了錯?
→ Lordaeron:不要但是了, 不看問題而回文, 也是
你在講什麼? 你說你的推文重要到值得看嗎?

抱歉,我只看原po的問題. 至於你自己製造的問題,請自己收拾.

→ yauhh:如果不要承認,那就不要囉唆囉,我還接到水球
→ Lordaeron:演算學者的大忌.
→ yauhh:要我加油,我就不知道是要加什麼油
※ 編輯: yauhh           來自: 59.112.227.2         (06/10 07:23)
→ Lordaeron:錯什麼? 我從沒說過我對過
→ Lordaeron:你真的要加油, 連原po 在問什麼都不知
→ Lordaeron:就回文了, 嗯演算學者的大忌.
→ Lordaeron:但還好, 我不是演算學者.
→ yauhh:你連推同一組推文二次,有什麼意義?
→ yauhh:我也不是演算學者啊
→ Lordaeron:原po 就在問這是不是NP 問題了,大哥
→ yauhh:他是問這問題是不是NP,而不是解法是不是NP.
→ Lordaeron:哇, 還有問題跟解法分離的說法?
→ Lordaeron:記住, 我是黑手, 不是學者, 沒大忌.沒差
→ yauhh:你第一篇回文只說像是P
→ yauhh:說錯了,你第一篇推文只說是P.
→ yauhh:所以你就是說,方法被抓到錯,不當一回事.
→ Lordaeron:是啊, 我推導如推文所述
→ yauhh:第二篇推文,你沒有提到P or NP.
→ yauhh:第三篇推文是我和原po的對話.
→ Lordaeron:不當一回事,有人連
→ Lordaeron:"問題是不是NP,而不是解法是不是NP"都跑
→ yauhh:第五篇推文,你根本沒有提P or NP.
→ Lordaeron:出來了. 再說, 我是黑手, 不是學者
→ yauhh:第六篇bob板友提問,你用回文方式處理,但是,
→ yauhh:但是你那篇回文雖然回了,但是解答中看得出
→ Lordaeron:不用但是了. 你的問題NP,解不NP, 我輸了
→ yauhh:漏餡漏很多. 自刪了.
→ Lordaeron:你繼續吧, 我們讀的書不同,沒什麼好講的
→ yauhh:至於現在你一直在說我不看人家的文,但是我
→ Lordaeron:加油.
→ yauhh:核對發現我都有看啊. 你的確沒有討論P or NP
→ yauhh:那你說說這個問題是不是NP?
→ yauhh:咦,我都已經這樣很有誠意跟你核對文章內容..
→ Lordaeron:問題NP or not, 解法NP or not, 想請問
→ yauhh:你到底在哪裏做了"是否為NP"的討論?
→ Lordaeron:出自何書之說, 讓我拜讀一下吧.
不好意思,不屑分享. 因為到此我感覺你很沒有誠意.

→ yauhh:我承認我並沒有討論NP. 那你說我該討論NP,
→ yauhh:為什麼你不討論呢?
※ 編輯: yauhh           來自: 59.112.227.2         (06/10 07:35)
→ Lordaeron:不屑分享. 因為到此我感覺你很沒有誠意.
→ Lordaeron:哈..............
→ yauhh:如果你不是心虛,不會這樣纏著我的推文不放.
→ yauhh:那我離開programming板囉,星期天要輕鬆,bye
→ Lordaeron:見鬼呢,連po問什麼都沒看就回文的人, 還
→ Lordaeron:可以說別人心虛,實在是佩服.
→ Lordaeron:這倒底是誰在鬧呢, hohoho..
推 sorryChen:實在不好意思, 讓兩位兄台替我費心了
→ Lordaeron:我的看法, 不是NP problem
→ Lordaeron:你去理哪個問題NP解NP 的幹嘛呢.
→ yauhh:可是是你自己去強調是否NP的,這會兒突然變
→ yauhh:別人去理NP不NP. 至於原po既然問了NP不NP,
→ yauhh:你又要後來否定原po的問題,你很矛盾耶.