作者lalawul (鋒哥開砲囉......)
看板logic
標題[請益] 智力測驗題目
時間Tue Mar 10 00:51:47 2009
朋友的小孩(國中)拿一題智力測驗裡的考題來問我
沒錯....我被問倒了......
Q: 給定N個正整數, 請將此N個正整數分成
兩群, 讓這兩群的正整數總合相等, 如果
無解, 則回答"無此種分法", 舉例來說
2, 4, 6, 12 就是分成(2,4,6),(12)
2, 4, 6, 11 就是無此種分法,
請問這有什麼規則可循嗎 ?
譬如說題目是 :
27 3 12 76 100 59 93 16 64 6 38 21
98 43 100 39 58 10 39 71 44 72 93
44 77 34 10 49 69 47
這要怎麼分呢 ?
THX.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.96.82
1F：推 cmlrdg:這好像是個NP-complete的問題說...@@ 03/10 01:56
2F：推 ksmrt0123:這是partition problem, 是NP-complete沒錯 03/10 02:41
3F：→ ksmrt0123:不過我想國中智力測驗這題肯定不是要求通解, 應該只是 03/10 02:43
4F：→ ksmrt0123:要學生根據給定的set (or multiset)找出一組解, 考考算 03/10 02:47
5F：→ ksmrt0123:術與簡單的思考吧... 假如題目真的如原po給的有那麼多個 03/10 02:48
6F：→ ksmrt0123:數字.. 看起來真是不太簡單... 03/10 02:48
7F：→ Hseuler:acm好像有類似題 03/10 22:27
8F：推 mikechan:全部和是奇數一定無解 03/15 03:10
9F：→ mikechan:所以有奇數個奇數一定無解 03/15 03:12
10F：推 KAOKAOKAO:一樣的可以先劃掉......吧？ 03/18 19:47
11F：推 KAOKAOKAO:......不行 03/20 17:41