[理工] [algo] 99台大資工第6題

[stustustu (stu蝦)]

題目:http://www.lib.ntu.edu.tw/exam/graduate/99/99405.pdf

自己是認為此題沒例子0.0

想法:因題目要求greedy的解要為minimum的兩倍
     但假設宇集合 u={1,2,3,4,5,6}
                  c={ c1={1,2,3} , c2={1,2,4} , c3={3,5} , c4={3,6}}

     這樣greedy就要挑c1,c2,c3,c4  ==>size=4
     而minimum為c2,c3,c4 ==>size=3
     不為兩倍

     希望有大大可以提出兩倍的例子...

     認為沒有的原因大概是第一題的6a要maximize  詳細的狀況很難用文字表達0.0...
     希望有人可以來個例子...感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.44.181.29
推 tureday:123
→ tureday:456
→ tureday:789
→ tureday:ABC
→ tureday:S1={1,2,3,4} ,S2={5,6,9},S3={7,8},S4={1,4,7,A},
→ tureday:S5={2,5,8,B},S6={3,6,9,C}
→ tureday:set挑的順序是S1S2S3S4S5S6，最佳解是S4S5S6，SIZE兩倍
→ stustustu:感謝樓上,例子超屌
推 cksh3300110:厲害~!
推 zelkova:不好意思, 借題目請問一下.. 6A是C', 6B是Ci 嗎?
推 cksh3300110:6A |R交集Ci|
推 zelkova:謝謝樓上幾位高手@@