PTT數位生活區 / Programming

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

看板Programming作者 (喲)時間12年前 (2012/06/10 06:35), 編輯推噓1(1推 0噓 83→)
留言84則, 3人參與, 最新討論串7/8 (看更多)
※ 引述《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)
→
06/10 06:56, , 1F
所以,你求出最佳解的做法是?
06/10 06:56, 1F
→
06/10 06:57, , 2F
再說, 1245的問題, 已經有人回了
06/10 06:57, 2F
→
06/10 06:57, , 3F
應該不用你發一篇文章來講,因為你還是
06/10 06:57, 3F
→
06/10 06:57, , 4F
後知後覺的哪位.
06/10 06:57, 4F
→
06/10 07:04, , 5F
我求不錯的解的做法,在我前文中第二方法中.
06/10 07:04, 5F
→
06/10 07:05, , 6F
至於所謂後知後覺,其實是不知不覺,因為我根
06/10 07:05, 6F
→
06/10 07:05, , 7F
本沒想要破解你的方法,是從理解你的方法之後
06/10 07:05, 7F
→
06/10 07:05, , 8F
看出漏餡之處.
06/10 07:05, 8F
→
06/10 07:06, , 9F
別人已經講過了. 你是沒看別人的回文?
06/10 07:06, 9F
→
06/10 07:07, , 10F
何苦去將他人的話轉述一次當作自己的呢
06/10 07:07, 10F
→
06/10 07:07, , 11F
那又怎麼樣?最起碼我發表了自己的破解解釋.
06/10 07:07, 11F
→
06/10 07:07, , 12F
對了,你還未證明你的做法是P, 不是NP
06/10 07:07, 12F
→
06/10 07:07, , 13F
要當算法高手, 還要證明哦.
06/10 07:07, 13F
→
06/10 07:08, , 14F
我不需要證明方法是NP,因為並沒有討論這一點
06/10 07:08, 14F
→
06/10 07:15, , 15F
你說我說的是別人講過的事情,對,因為在本文
06/10 07:15, 15F
→
06/10 07:15, , 16F
張貼之前,我根本看不懂你的方法究竟怎麼做.
06/10 07:15, 16F
→
06/10 07:16, , 17F
你描述的時候前後說詞修來修去,黑手動作多,
06/10 07:16, 17F
→
06/10 07:17, , 18F
是到前一位bob板友質疑才看明白你所講的.
06/10 07:17, 18F
→
06/10 07:17, , 19F
你看不懂沒關係,有別人看出問題了
06/10 07:17, 19F
→
06/10 07:18, , 20F
可見你講了這個方法有多難懂.
06/10 07:18, 20F
→
06/10 07:18, , 21F
你不知不覺而已,再說是不是NP才是發
06/10 07:18, 21F
→
06/10 07:18, , 22F
問者的重點,你連別人問什麼都不知,回
06/10 07:18, 22F
→
06/10 07:18, , 23F
講方法講的別人不懂,這也是演算學者的大忌.
06/10 07:18, 23F
→
06/10 07:19, , 24F
得比我還要爽, 實在是佩服.
06/10 07:19, 24F
→
06/10 07:19, , 25F
少來一套,你也沒有解釋你的方法是不是NP.
06/10 07:19, 25F
→
06/10 07:20, , 26F
為什麼我突然要回答方法是不是NP?
06/10 07:20, 26F
→
06/10 07:20, , 27F
哈....你真的是一個不看文的人.....不行
06/10 07:20, 27F
→
06/10 07:20, , 28F
不看文而回文,是回文的大忌
06/10 07:20, 28F
→
06/10 07:20, , 29F
你是說你推文中說你方法是P那樣子嗎?但是,
06/10 07:20, 29F
→
06/10 07:20, , 30F
請回去看原po 的問題, 謝謝囉.
06/10 07:20, 30F
→
06/10 07:21, , 31F
你的方法錯,所以P或NP,沒用,不是嗎?
06/10 07:21, 31F
→
06/10 07:21, , 32F
那你到底要不要承認你犯了錯?
06/10 07:21, 32F
→
06/10 07:21, , 33F
不要但是了, 不看問題而回文, 也是
06/10 07:21, 33F
你在講什麼? 你說你的推文重要到值得看嗎? 抱歉,我只看原po的問題. 至於你自己製造的問題,請自己收拾.
→
06/10 07:21, , 34F
如果不要承認,那就不要囉唆囉,我還接到水球
06/10 07:21, 34F
→
06/10 07:22, , 35F
演算學者的大忌.
06/10 07:22, 35F
→
06/10 07:22, , 36F
要我加油,我就不知道是要加什麼油
06/10 07:22, 36F
※ 編輯: yauhh 來自: 59.112.227.2 (06/10 07:23)
→
06/10 07:22, , 37F
錯什麼? 我從沒說過我對過
06/10 07:22, 37F
→
06/10 07:23, , 38F
你真的要加油, 連原po 在問什麼都不知
06/10 07:23, 38F
→
06/10 07:23, , 39F
就回文了, 嗯演算學者的大忌.
06/10 07:23, 39F
→
06/10 07:23, , 40F
但還好, 我不是演算學者.
06/10 07:23, 40F
→
06/10 07:24, , 41F
你連推同一組推文二次,有什麼意義?
06/10 07:24, 41F
→
06/10 07:24, , 42F
我也不是演算學者啊
06/10 07:24, 42F
→
06/10 07:24, , 43F
原po 就在問這是不是NP 問題了,大哥
06/10 07:24, 43F
→
06/10 07:25, , 44F
他是問這問題是不是NP,而不是解法是不是NP.
06/10 07:25, 44F
→
06/10 07:25, , 45F
哇, 還有問題跟解法分離的說法?
06/10 07:25, 45F
→
06/10 07:26, , 46F
記住, 我是黑手, 不是學者, 沒大忌.沒差
06/10 07:26, 46F
→
06/10 07:26, , 47F
你第一篇回文只說像是P
06/10 07:26, 47F
→
06/10 07:26, , 48F
說錯了,你第一篇推文只說是P.
06/10 07:26, 48F
→
06/10 07:27, , 49F
所以你就是說,方法被抓到錯,不當一回事.
06/10 07:27, 49F
→
06/10 07:27, , 50F
是啊, 我推導如推文所述
06/10 07:27, 50F
→
06/10 07:27, , 51F
第二篇推文,你沒有提到P or NP.
06/10 07:27, 51F
→
06/10 07:27, , 52F
第三篇推文是我和原po的對話.
06/10 07:27, 52F
→
06/10 07:28, , 53F
不當一回事,有人連
06/10 07:28, 53F
→
06/10 07:28, , 54F
"問題是不是NP,而不是解法是不是NP"都跑
06/10 07:28, 54F
→
06/10 07:28, , 55F
第五篇推文,你根本沒有提P or NP.
06/10 07:28, 55F
→
06/10 07:28, , 56F
出來了. 再說, 我是黑手, 不是學者
06/10 07:28, 56F
→
06/10 07:28, , 57F
第六篇bob板友提問,你用回文方式處理,但是,
06/10 07:28, 57F
→
06/10 07:29, , 58F
但是你那篇回文雖然回了,但是解答中看得出
06/10 07:29, 58F
→
06/10 07:29, , 59F
不用但是了. 你的問題NP,解不NP, 我輸了
06/10 07:29, 59F
→
06/10 07:29, , 60F
漏餡漏很多. 自刪了.
06/10 07:29, 60F
→
06/10 07:30, , 61F
你繼續吧, 我們讀的書不同,沒什麼好講的
06/10 07:30, 61F
→
06/10 07:30, , 62F
至於現在你一直在說我不看人家的文,但是我
06/10 07:30, 62F
→
06/10 07:30, , 63F
加油.
06/10 07:30, 63F
→
06/10 07:30, , 64F
核對發現我都有看啊. 你的確沒有討論P or NP
06/10 07:30, 64F
→
06/10 07:31, , 65F
那你說說這個問題是不是NP?
06/10 07:31, 65F
→
06/10 07:33, , 66F
咦,我都已經這樣很有誠意跟你核對文章內容..
06/10 07:33, 66F
→
06/10 07:33, , 67F
問題NP or not, 解法NP or not, 想請問
06/10 07:33, 67F
→
06/10 07:33, , 68F
你到底在哪裏做了"是否為NP"的討論?
06/10 07:33, 68F
→
06/10 07:34, , 69F
出自何書之說, 讓我拜讀一下吧.
06/10 07:34, 69F
不好意思,不屑分享. 因為到此我感覺你很沒有誠意.
→
06/10 07:34, , 70F
我承認我並沒有討論NP. 那你說我該討論NP,
06/10 07:34, 70F
→
06/10 07:34, , 71F
為什麼你不討論呢?
06/10 07:34, 71F
※ 編輯: yauhh 來自: 59.112.227.2 (06/10 07:35)
→
06/10 07:36, , 72F
不屑分享. 因為到此我感覺你很沒有誠意.
06/10 07:36, 72F
→
06/10 07:36, , 73F
哈..............
06/10 07:36, 73F
→
06/10 07:37, , 74F
如果你不是心虛,不會這樣纏著我的推文不放.
06/10 07:37, 74F
→
06/10 07:38, , 75F
那我離開programming板囉,星期天要輕鬆,bye
06/10 07:38, 75F
→
06/10 07:40, , 76F
見鬼呢,連po問什麼都沒看就回文的人, 還
06/10 07:40, 76F
→
06/10 07:41, , 77F
可以說別人心虛,實在是佩服.
06/10 07:41, 77F
→
06/10 07:42, , 78F
這倒底是誰在鬧呢, hohoho..
06/10 07:42, 78F
推
06/11 15:21, , 79F
實在不好意思, 讓兩位兄台替我費心了
06/11 15:21, 79F
→
06/11 16:21, , 80F
我的看法, 不是NP problem
06/11 16:21, 80F
→
06/11 16:21, , 81F
你去理哪個問題NP解NP 的幹嘛呢.
06/11 16:21, 81F
→
07/01 19:43, , 82F
可是是你自己去強調是否NP的,這會兒突然變
07/01 19:43, 82F
→
07/01 19:44, , 83F
別人去理NP不NP. 至於原po既然問了NP不NP,
07/01 19:44, 83F
→
07/01 19:44, , 84F
你又要後來否定原po的問題,你很矛盾耶.
07/01 19:44, 84F
‣ 更多 yauhh 的文章
文章代碼(AID): #1Fqy_39C (Programming)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 7 之 8 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共8篇)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 yauhh 的文章
文章代碼(AID): #1Fqy_39C (Programming)