這個謎題子集的總和？

Question

在衛報（英國報紙）今天的版本，由克里斯·MASLANKA 43頁的「Pyrgic困惑」一節中，下面的拼圖給定：

3個智者...去到Herrods去做他們的聖誕節購物。 Caspar買了Gold，Melchior買了Frankincense，Balthazar買了的Daily Daily Myrrh。收銀員用這些東西的歐元數量付出代價，並且意味着增加三個數字，但是將它們相乘。 ......事情的奇蹟在於結果完全一樣：65.52歐元。這三個數字是什麼（我認爲他的意思是三個數字]？

我的解釋是：查找一個，b和Ç使得一個 + b + Ç = ABC = 65.52（精確地）其中一個， b和c是正數十進制數，不超過兩位小數。因此，a,b和c也必須小於65.52（大約）。

我的做法是這樣的：我會找到所有的候選集的一個，b和ç其中一個 + b + Ç = 6552和一個，b和c是來自{1 ... 6550}的整數（爲了方便起見，我將所有操作數乘以100）。然後，對於所有候選集合，通過將所有操作數除以100然後將其相乘（使用任意精度算法）來滿足另一個條件是微不足道的。

這就如我所見，是子集求和問題的一個實例。所以我實現了一個骯髒的（指數時間）算法，它找到了一個不同的解決方案：a = 0.52，b = 2，c = 63。

好的，對於子集求和問題，有更好的算法，但是你不覺得這對於一個普通的Guardian讀者來說有點過分了嗎？

在第40頁的答案列出：

這是很容易，通過試驗和錯誤。猜猜52p爲每日沒藥。但乘以0.52大致減半，所以我們需要一個總和約爲2;所以試試2 X 63 X 0.52。 Etvoilà。這個答案是唯一的嗎？

那麼，我們知道答案是獨一無二的（不考慮2,63和0.52的其他排列）。

我想知道的是：這怎麼可能「輕鬆」？我是否正確地將謎題描述爲子集總和問題的一個實例？我是否忽略了可用於簡化解決方案的難題的一些特徵？是否有人能夠採用類似的「試錯法」方法，如果可以的話，他們能否接受我？克里斯馬斯蘭卡是否完全沒有NP完全問題？

Answer 1

不，這不是子集和問題的一個實例，這是因爲：

1. 子集大小被限制爲3，使得它O(n^3)溶液最壞與幼稚窮舉搜索（而不是指數）的情況下
2. 這裏還有其他數據，數字的產品。
3. 你實際上沒有給出一組集合，所有整數的集合只是subset-sum的一個子問題，更容易一個。

這裏要理解的重要一點是：如果問題可以通過NP-Hard問題解決 - 它並不意味着它也是NP-Hard，反之亦然 - 如果您擁有問題，你可以用它解決一些NP-Hard問題（多項式），那麼你的問題是NP-Hard。它被稱爲polynomial reduction 。

---

的方法很簡單，因爲所有你需要做的是「猜測」（通過遍歷所有候選人）的數值爲a，從這個你可以得到什麼是b，c可能的解決方法 - （2變量，如果知道a這兩個方程 - 在每次迭代中 - 它是），因此解甚至是線性的 - 不僅是次指數。

它甚至可以優化使用二進制搜索的變體來獲得亞線性優化，但我現在還無法想到該優化。

---

（1）注意：這是一些直觀的解釋，而不是一個正式的定義。 「