这个谜题子集的总和？

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）注意：这是一些直观的解释，而不是一个正式的定义。 “