[請益] 智力測驗題目

[lalawul (鋒哥開砲囉......)]

朋友的小孩(國中)拿一題智力測驗裡的考題來問我
沒錯....我被問倒了......

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
推 cmlrdg:這好像是個NP-complete的問題說...@@
推 ksmrt0123:這是partition problem, 是NP-complete沒錯
→ ksmrt0123:不過我想國中智力測驗這題肯定不是要求通解, 應該只是
→ ksmrt0123:要學生根據給定的set (or multiset)找出一組解, 考考算
→ ksmrt0123:術與簡單的思考吧... 假如題目真的如原po給的有那麼多個
→ ksmrt0123:數字.. 看起來真是不太簡單...
→ Hseuler:acm好像有類似題
推 mikechan:全部和是奇數一定無解
→ mikechan:所以有奇數個奇數一定無解
推 KAOKAOKAO:一樣的可以先劃掉......吧？
推 KAOKAOKAO:......不行