如果行得通的话你已经证明 P = NP... :p 这题是 subset sum problem 的变形, 要找到 polynomial-time reduction 并不难. http://en.wikipedia.org/wiki/Subset_sum_problem 想法是这样: 输入为 {x_1, ..., x_n}, 取一补正值 K > n*max(|x_i|), 假设存在一组解 {y_1, ..., y_m} 共 m 个数, 对於 m <= 2 的情形直接穷举就可以了, 对於 m > 2 的情形可产生下列资料作为变化版问题的输入: {-x_1 + (m-1)*K, x_2+K, x_3+K, ..., x_n+K} {x_1+K, -x_2 + (m-1)*K, x_3+K, ..., x_n+K} ... {x_1+K, x_2+K, x_3+K, ..., -x_n + (m-1)*K} 这 n 组资料中若任何一组有解, 其解必为以 -x_a + (m-1)*K 带头的 m 个数, (证明略, 基本上是利用 K 很大, 就算全部 x_i 加起来都没办法抵过一个 K 的差. 一个特例是当存在 x_i = x_j 的情形, 这比较难搞, 在此假定 x_1 ... x_n 不重复, 但是重复的情形还是证明得出来) 也就是说 -x_a + (m-1)*K = x_b+K + x_c+K + x_d+K + ... 等式两边移一下可以找到 x_a + x_b + x_c + x_d + ... = 0 作为原 subset sum problem 的答案. 只要对於所有可能的 m 试过一遍, 这样就解了 subset sum problem. 故得证该面试问题为 NP-hard. 话是如此啦, 但我猜原本面试想考的应该是 pseudo-polynomial time 的解法, 当值域不大的时候你可以在值域内用 dynamic programming 来解. http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution 评: 这题大约是高中竞赛的难度, 理论证明要等到硕一上完计算复杂度理论. (总之是基本工啦) ※ 引述《eshai (暖暖的 ^^)》之铭言： : 前後文恕删，刚好在这网站看到有点类似的题目跟解题想法，给有兴趣的版友参考一下: : 先把集合理面的数字 sorting, 然後在往较小的 subset 里面做测试 : 我觉得概念上来讲是行得通的 : (还是很麻烦，但是答起来听起来就比较 oraginized) : : Find a subset in a array that the biggest number is sum of rest of the subset : : ex: : : {3, 4, 9, 14, 15, 19, ...} : : {4, 15, 19} 就是19=4+15，是合格的subset : : 这题最难的是他的数字有二十几个，光是要计算power set就让人很头大 : : 复杂度是2^n，把我的记忆体全部用光光orz : http://www.careercup.com/question?id=14366691 : Q: there are list of random numbers like 1,3,23,76,908,34,256,12,43,11,2,-10 : given an input suppose:13 : find the combination of the numbers which adds up to 13. : like 1+12=13,23+(-10)=13..like that : A: It can be done as follows. : 1. Sort the list in ascending order (takes O(nlgn)) : 2. Read the list from begining : 3. For each element read search (13 - element read) value from the list. : Seaching in list takes lgn and in worst case the time complexity : will be O(nlgn) -- 「ふ…ふざけるな！そんあ短い咒文で、魔法を起动できるわけないだろうが！ お前わマウゼルの神に逆らう气なのか？！傲慢な～」 「失礼致しました、诚实に全力でお相手致します。 第一战术级‧军用攻性魔法‧出よ、武雷神〈トール〉！」 〈スクラップド‧プリンセス〉 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 216.239.45.4