algorithm - 旧 Top Coder 谜语的复杂性 : Making a number by inserting +

Question

这是对 my previous question 的跟进(关于一个古老的顶级程序员谜语)。

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual.

For example, consider "303" and a target sum of 6. The best strategy is "3+03".

我猜(虽然没有证明)这个问题是 NP 完全的。你怎么认为？您如何将一个众所周知的 NP 完全问题归结为这个问题？

Answer 1

如果将基作为参数，则子集总和会减少。令 x₁, …, x_n, s > 0 为子集和的实例并令 S = x₁ + … + x<子>n 。在基础 S + 1 中，让 Top Coder 输入为

x₁ 0 x₂ 0 ... x_n 0

求和为 (S - s) (S + 1) + s。

当然，更有趣的是 10 进制表壳的硬度。