如果行得通的話你已經證明 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