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

看板Grad-ProbAsk作者stustustu (stu蝦)時間15年前 (2011/01/29 23:01)推噓5(5推 0噓 7→)

留言12則, 4人參與討論串1/1

題目: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

01/30 00:46, , 1^F

01/30 00:46, 1^F

→

tureday

01/30 00:46, , 2^F

01/30 00:46, 2^F

→

tureday

01/30 00:46, , 3^F

01/30 00:46, 3^F