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

Question

这是对我之前的问题（关于一个旧的顶级编码器之谜）的跟进。

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

例如，考虑“303”和目标总和为 6。最佳策略是“3+03”。

我猜（虽然没有证明）问题是NP完全的。你怎么看？你如何将一个众所周知的 NP 完全问题简化为这个问题？

Answer 1

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

Answer 2

如果将基数设为参数，则子集总和会有所减少。令 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 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”）。