古老的 Top Coder 谜语的复杂性：通过插入 + 来生成数字

Question

这是我之前的问题的后续问题（关于一个古老的顶级程序员之谜）。

给定一串数字，找到该字符串等于某个目标数字所需的最小加法次数。每次添加都相当于在数字字符串中的某处插入一个加号。插入所有加号后，照常计算总和。

例如，考虑“303”和目标总和为 6。最佳策略是“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。

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

Answer 2

如果您在数字后添加预期结果，很明显这是 http://en.wikipedia.org /wiki/Partition_problem ？

Answer 3

这是为求知欲强（或懒惰）的人提供的解决方案代码。
JavaScript：

var A = "12345";

function riddle(s, n) {
 for(var ins=0; ins<s.length; ins++) {
  if( recurse(n, "", s, ins) ) {
   console.log(ins + " insertions");
   break;
  }
 }
}

function recurse(n, t, s, ins) {
 if(ins == 0) {
 // reached the end does it equal the number?
  var temp = (t != "" ? t + " + " : "") + s;
  if( eval(temp) == n ) {
   console.log(temp);
   return true;
  }
  return false;
 } else if(s.length - ins > 0) {
  for(var x=1; x<s.length; x++) {
   var temp = (t != "" ? t + " + " : "") + s.substring(0, x);
   if( recurse(n, temp, s.substring(x), ins-1) ) {
    return true;
   }
  }
 }
 return false;
}

riddle(A, 12345);
riddle(A, 357);
riddle(A, 15);

指数时间，可能性数为2^(n-1)，当n = 3时，T(n) = 4；当n = 5时，T(n) = 32。

如果考虑插入次数与集合大小相对应，并且这些插入的位置是集合元素，您可以看到与子集和的关系。此外，与 Subset Sum 一样，验证器是多项式时间，只需对数字集求和（上面代码中的“eval(temp) == n”）。