Загадка Old Top Coder: сделать число, вставив +

Question

Я думаю о этой проблеме topcoder .

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

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

Я бы решил это с помощью грубой силы следующим образом:

for each i in 0 to 9 // i -- number of plus signs to insert
  for each combination c of i from 10
    for each pos in c // we can just split the string w/o inserting plus signs
      insert plus sign in position pos 
    evaluate the expression
    if the expression value == given sum
      return i

Имеет ли это смысл? Оптимален ли он с точки зрения производительности?

...

Что ж, теперь я вижу, что решение для динамического программирования будет более эффективным. Однако интересно, если представленное решение все равно имеет смысл.

Answer 1

Это, конечно, не оптимально. Если, например, вам дана строка «1234567890», а целью является трехзначное число, вы знаете, что нужно разбить строку как минимум на четыре части, поэтому вам не нужно проверять вставки 0, 1 или 2 , Кроме того, цель ограничивает диапазон допустимых позиций ввода. Обе точки имеют небольшое влияние на короткие струны, но могут иметь огромное значение для более длинных. Тем не менее, я подозреваю, что есть гораздо лучший метод, немного пахнет DP.

Answer 2

Я еще не задумывался об этом, но если вы прокрутите вниз, вы увидите ссылку на конкурс, из которого он был, и оттуда вы увидите решения для решателей. Вот один в C #.

using System; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Collections; 

public class QuickSums { 
    public int minSums(string numbers, int sum) { 
        int[] arr = new int[numbers.Length]; 
    for (int i = 0 ; i < arr.Length; i++)       
      arr[i] = 0; 

    int min = 15; 

    while (arr[arr.Length - 1] != 2)     
    { 
      arr[0]++; 
      for (int i = 0; i < arr.Length - 1; i++) 
        if (arr[i] == 2)  
        { 
          arr[i] = 0; 
          arr[i + 1]++; 
        } 

      String newString = ""; 
      for (int i = 0; i < numbers.Length; i++) 
      { 
        newString+=numbers[i]; 
        if (arr[i] == 1) 
          newString+="+"; 
      } 

      String[] nums = newString.Split('+'); 
      int sum1 = 0; 
      for (int i = 0; i < nums.Length; i++) 
        try  
        { 
          sum1 += Int32.Parse(nums[i]); 
        } 
        catch 
        { 
        } 

      if (sum == sum1 && nums.Length - 1 < min) 
        min = nums.Length - 1; 
    } 

    if (min == 15) 
      return -1; 

    return min; 
  } 

} 

Answer 3

Кажется, уже слишком поздно ... но просто прочитайте некоторые комментарии и ответы, которые говорят "нет" подходу к дп.Но это очень простой дп, похожий на задачу резания стержня:

Чтобы понять суть:

int val[N][N];
int dp[N][T];

val[i][j]: numerical value of s[i..j] including both i and j

val[i][j] can be easily computed using dynamic programming approach in O(N^2) time

dp[i][j] : Minimum no of '+' symbols to be inserted in s[0..i] to get the required sum j

dp[i][j] = min( 1+dp[k][j-val[k+1][j]] ) over all k such that 0<=k<=i and val[k][j]>0

Проще говоря, для вычисления dp [i] [j] вы принимаетепозиция k последнего символа '+' и затем повторение для s [0..k]

Answer 4

динамическое программирование:

public class QuickSums {

public static int req(int n, int[] digits, int sum) {

    if (n == 0) {
        if (sum == 0)
            return 0;
        else
            return -1;
    } else if (n == 1) {
        if (sum == digits[0]) {
            return 0;
        } else {
            return -1;
        }
    }

    int deg = 1;
    int red = 0;

    int opt = 100000;
    int split = -1;

    for (int i=0; i<n;i++) {
        red += digits[n-i-1] * deg;

        int t = req(n-i-1,digits,sum - red);
        if (t != -1 && t <= opt) {
            opt = t;
            split = i;
        }
        deg = deg*10;
    }

    if (opt == 100000) 
        return -1;
    if (split == n-1) 
        return opt;
    else
        return opt + 1;

}

public static int solve (String digits,int sum) {
   int [] dig = new int[digits.length()];
   for (int i=0;i<digits.length();i++) {
       dig[i] = digits.charAt(i) - 48;
   }

    return req(digits.length(), dig, sum);
}


public static void doit() {
    String digits = "9230560001";
    int sum = 71;

    int result = solve(digits, sum);
    System.out.println(result);
}

Answer 5

Я думаю, что проблема похожа на проблему умножения цепочки матриц, где мы должны поставить скобки для наименьшего умножения.Здесь фигурные скобки представляют «+».Поэтому я думаю, что это может быть решено с помощью аналогичного подхода дп .. Попробую реализовать его.

Answer 6

Поскольку длина ввода мала (10), все возможные пути (которые можно найти с помощью простого двоичного счетчика длины 10) малы (2 ^ 10 = 1024), поэтому ваш алгоритм достаточно быстр и возвращает действительный результат, иИМО нет необходимости его улучшать.

В целом, пока ваше решение не будет работать нормально во времени, памяти и других данных ограничениях, нет необходимости выполнять микрооптимизацию.например, этот случай, предлагаемый akappa, может быть решен с помощью DP, как DP, в задаче с двумя разделами, но когда ваш алгоритм работает быстро, нет необходимости делать это и может быть добавление некоторой большой константы или невозможность чтения кода.

Я просто предлагаю один раз проанализировать цифры строки (в массиве длиной 10), чтобы предотвратить слишком много разборов строк, и просто использовать * 10 ^ k + ... (Также вы можете вычислить 10 ^ k для k = 0 ..9 при запуске и сохранить его значение).