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

[Lordaeron (Terry)]

※ 引述《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
→ yauhh:你刪了卻還要統計刪了哪些,然後再重新找答案
→ yauhh:在你解釋範圍中,演算法看起來越來越繁雜.
→ Lordaeron:你看不懂, 正如你有問題NP, 解NP一樣.
→ Lordaeron:只有NP problem,但你發明了NP solution
→ Lordaeron:不同星球的, 很難溝通的
→ yauhh:還在撐啊,你這方法根本沒用,還一直補充?
→ yauhh:然後我並沒有很堅持說有所謂NP solution,
→ yauhh:你可以不必一直抬轎.
→ Lordaeron:沒用? 哪請你來證明沒用啊.
→ Lordaeron:你是發明了NP solution的高人呢.
→ Lordaeron:再說,我又沒回你, 是你來抬摃吧.
推 yauhh:請你搞清楚,你這個題目的算法並沒有回答正確
→ yauhh:但後來卻是你這個答錯的人不時在說"多看算法
→ yauhh:的書吧" 這一類的話. 自己答錯,卻好愛跑出來
→ yauhh:當人的老師,推文大亂鬥. 捫心自問,這樣是否
→ yauhh:為一位專業者可以表現出的資態?
→ yauhh:我是覺得,一個不知道或不承認自己錯誤的人,
→ yauhh:講那什麼道理是沒什麼說服力可言的.
→ yauhh:快點長大吧,小鬼.