Re: 算法問題 (從N個set選m個包含最少的元素)
※ 引述《sorryChen (陳揚和)》之銘言：
: ※ 引述《sorryChen (陳揚和)》之銘言：
: : 給定N個set, 規定至少個set, 使選的sets的集合包含的element個數越少越好
: 請原諒不太懂推文中所寫的所以舉例一下
: ex: S0={0}, S1={1}, S2={2},S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={1,3}
: 假設都排好了
: M=4好了, 選S1,S2,S4,S5
: M=7好了, 選S1,S2,S3,S4,S5,S6,S7, 反正不選S0, 想說排序選前面的不見得最好
借你這個例子,忽略掉你所問的推文問題,我的粗淺想法是:
1. 取指定集合數M: 在此為3.
2. 隨便取第一個M sets, 做一個binding B, 對應到M sets包含的全部元素:
取 S0={0}, S1={1}, S2={2} ===> B = { {S0, S1, S2}, {0, 1, 2} }
3. 取下一個集合 S4 = {1, 2}.
4. 問 S4 替換掉 S0, S1, S2 之一, 會不會減少M sets元素數目:
4-1. { {S4, S1, S2}, {1, 2} } 減少了元素數目.
4-2. { {S0, S4, S2}, {0, 1, 2} } 沒有減少元素數目.
4-3. { {S0, S1, S4}, {0, 1, 2} } 沒有減少元素數目.
4-4. 經過以上核對, 取 {S1, S2, S4} 為M sets.
5. 如果有其餘集合, 回到3.
--------- 這個解決辦法的另一種解釋 -------------
取(N,M)組合,例如(8,3)組合,依序求聯集,看有沒有出現元素量更少的聯集:
S0 S1 S2 S3 S4 S5 S6 S7
* * * {0,1,2}
* * * {0,1,3}
* * * {0,1,2}
......
* * * {1,2}
其中要用到的基礎運算單元就是聯集運算和差集運算了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.228.180
※ 編輯: yauhh 來自: 59.112.228.180 (06/01 22:16)
推
06/02 04:27, , 1F
06/02 04:27, 1F
→
06/02 04:28, , 2F
06/02 04:28, 2F
→
06/02 04:28, , 3F
06/02 04:28, 3F
→
06/02 08:17, , 4F
06/02 08:17, 4F
→
06/02 08:19, , 5F
06/02 08:19, 5F
推
06/02 10:53, , 6F
06/02 10:53, 6F
推
06/02 10:57, , 7F
06/02 10:57, 7F
→
06/02 10:57, , 8F
06/02 10:57, 8F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 8 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
