作者Lordaeron (Terry)
站內Programming
標題Re: 算法問題 (從N個set選m個包含最少的元素)
時間Tue Jun 12 10:30:45 2012
※ 引述《bob123 ()》之銘言：
: ※ 引述《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 最大的
: 不知道我有沒有誤解,在您的演算法中
: 好像刪元素的順序是關鍵
: 所以想請教一下
: 上例刪重複元素的順序為 元素1,2,3
: 不先刪0是因為0的個數比1,2,3少嗎
: 若是如此 今天新加入 S8 = {0,108,208,308},
: S9 = {0,109,209,309},
: S10 = {0,110,210,310}
: 這演算法就無效了嗎?
所以0,1,2 被刪4 個, 3 被刪3 個.
所以, 從帶有0,1,2, 且被刪空掉的集合中找出答案囉.
有S0,S1,S2,S4,S5, 哪看來是, S1,S2,S4,S5 囉.
因S4,S5 兩elements, 故先取, 再找跟S4/S5 有相同element 的. 故S1,S2.
哪麼, 比較麻煩的是, 若有S11={0,1,2},S12={0,1,2},S13={0,1},S14={0,1} 囉.
哪是找最小的集合囉.
帶, 1,2 的兩個
帶, 0,1 的兩個
帶 0,1,2 的兩個
....
這樣找下去, 也不用指數時間, 還是會有答案.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.59.250.101
1F：→ yauhh:你刪了卻還要統計刪了哪些,然後再重新找答案 61.231.64.224 06/12 19:27
2F：→ yauhh:在你解釋範圍中,演算法看起來越來越繁雜. 61.231.64.224 06/12 19:28
3F：→ Lordaeron:你看不懂, 正如你有問題NP, 解NP一樣. 1.162.14.217 06/12 22:10
4F：→ Lordaeron:只有NP problem,但你發明了NP solution 1.162.14.217 06/12 22:14
5F：→ Lordaeron:不同星球的, 很難溝通的 1.162.14.217 06/12 22:14
6F：→ yauhh:還在撐啊,你這方法根本沒用,還一直補充? 61.231.64.224 06/12 23:13
7F：→ yauhh:然後我並沒有很堅持說有所謂NP solution, 61.231.64.224 06/12 23:14
8F：→ yauhh:你可以不必一直抬轎. 61.231.64.224 06/12 23:14
9F：→ Lordaeron:沒用? 哪請你來證明沒用啊. 1.162.14.217 06/13 00:49
10F：→ Lordaeron:你是發明了NP solution的高人呢. 1.162.14.217 06/13 00:50
11F：→ Lordaeron:再說,我又沒回你, 是你來抬摃吧. 1.162.14.217 06/13 00:50
12F：推 yauhh:請你搞清楚,你這個題目的算法並沒有回答正確 59.112.231.99 07/01 19:55
13F：→ yauhh:但後來卻是你這個答錯的人不時在說"多看算法 59.112.231.99 07/01 19:56
14F：→ yauhh:的書吧" 這一類的話. 自己答錯,卻好愛跑出來 59.112.231.99 07/01 19:56
15F：→ yauhh:當人的老師,推文大亂鬥. 捫心自問,這樣是否 59.112.231.99 07/01 19:57
16F：→ yauhh:為一位專業者可以表現出的資態? 59.112.231.99 07/01 19:57
17F：→ yauhh:我是覺得,一個不知道或不承認自己錯誤的人, 59.112.231.99 07/01 19:59
18F：→ yauhh:講那什麼道理是沒什麼說服力可言的. 59.112.231.99 07/01 19:59
19F：→ yauhh:快點長大吧,小鬼. 59.112.231.99 07/01 19:59