作者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