Сложность старой загадки Top Coder: сделать число, вставив +

Question

Это продолжение до моего предыдущего вопроса (о старой загадке верхнего кодера).

Учитывая строку цифр, найдите минимальное количество дополнений, необходимое для того, чтобы строка равнялась некоторому целевому числу.Каждое добавление эквивалентно вставке знака плюс в строку цифр.После того, как все знаки плюс вставлены, оцените сумму как обычно.

Например, рассмотрите «303» и целевую сумму 6. Лучшая стратегия - «3 + 03».

Я полагаю (хотя это и не доказано), проблема является NP-полной.Как вы думаете?Как бы вы свели к этой проблеме хорошо известную NP-полную проблему?

Answer 1

Если для базы задан параметр, то происходит уменьшение от подмножества суммы.Пусть x ₁ ,…, x _n , s> 0 будет экземпляром подмножества суммы, и пусть S = x ₁ +… + x _n.В базе S + 1 пусть вход верхнего кодера будет

x ₁ 0 x ₂ 0… x _n 0

суммирование в (S - s) (S + 1) + s.

Гораздо интереснее, конечно, твердость случая с основанием 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» в приведенном выше коде).