Разобрать строку, чтобы сформировать правильное выражение

Question

Мне дана строка S (целых чисел) и число N .Я хочу вставить произвольное число '+' в S , чтобы сумма стала равной N .

Ex:<br>
S = 15112 and N = 28<br>
Ans is : 15+11+2<br>
S = 120012 and N = 33<br>
Ans is : 1+20+012<br>
S = 123 and N = 123<br>
Ans is : 123

, учитывая: | S |<= 120 и N <= 10 ^ 6 <Br>Гарантируется, что S и N даны так, что всегда можно сформировать правильное выражение.Есть ли алгоритм, который может решить эту проблему?Я пытался обдумать это, но не смог найти решение.

Answer 1

Это Ruby-версия с пошаговым объяснением алгоритма, так что вы можете легко писать код на C ++ (или я попробую позже).

# Let's consider that we extracted the values from text, so we already have the string of int and the result as integer:

string_of_int = "15112"
result = 28

# The basic idea is to find a map (array) that tells how to group digits, for example

sum_map = [2, 1, 2]

# This means that string_of_int is mapped into the following numbers
# 15, 1, 12
# then sum the numbers, in this case 15+1+12 = 28

# For finding a the solution we need to map
# all the possible combinations of addition given the n digits of the string_of_int then check if the sum is equal to the result

# We call k the number of digits of string_of_int
# in ruby we can build an array called sum_maps
# containing all the possible permutations like this:

k = string_of_int.length # => 5
sum_maps = []
k.times do |length|
  (1..k).to_a.repeated_permutation(length).each {|e| sum_maps << e if e.inject(:+) == k}
end
sum_maps
# => [[1, 5], [2, 4], [3, 3], [4, 2], [5, 1], [1, 1, 4], [1, 2, 3], [1, 3, 2], [1, 4, 1], [2, 1, 3], [2, 2, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1], [4, 1, 1]]

# Now must check which of of the sum_map is giving us the required result.
#
# First, to keep the code short and DRY,
# better to define a couple of useful methods for the String class to use then:

class String
  def group_digits_by(sum_map)
    string_of_int_splitted = self.split("")
    grouped_digits = []
    sum_map.each { |n| grouped_digits << string_of_int_splitted.shift(n).join.to_i}
    grouped_digits.reject { |element| element == 0 }
  end

  def sum_grouped_of_digits_by(sum_map)
    group_digits_by(sum_map).inject(:+)
  end
end

# So we can call the methods directly on the string
# for example, in ruby:

string_of_int.group_digits_by sum_map #=> [15, 1, 12]
string_of_int.sum_grouped_of_digits_by sum_map #=> 28

# Now that we have this metods, we just iterate through the sum_maps array
# and apply it for printing out the sm_map if the sum of grouped digits is equal to the result
# coded in ruby it is:

combinations = []
sum_maps.each { |sum_map| combinations << string_of_int.group_digits_by(sum_map) if string_of_int.sum_grouped_of_digits_by(sum_map) == result }
p combinations.uniq
# => [[15, 1, 12], [15, 11, 2]]

* 1006Короче говоря, в виде модуля Ruby он становится:

module GuessAddition
  class ::String
    def group_digits_by(sum_map)
      string_of_int_splitted = self.split("")
      grouped_digits = []
      sum_map.each { |n| grouped_digits << string_of_int_splitted.shift(n).join.to_i}
      grouped_digits.reject { |element| element == 0 }
    end
    def sum_grouped_of_digits_by(sum_map)
      group_digits_by(sum_map).inject(:+)
    end
  end
  def self.guess_this(string_of_int, result)
    k = string_of_int.length
    sum_maps = []
    k.times { |length| (1..k).to_a.repeated_permutation(length).each {|e| sum_maps << e if e.inject(:+) == k} }
    combinations = []
    sum_maps.each { |sum_map| combinations << string_of_int.group_digits_by(sum_map) if string_of_int.sum_grouped_of_digits_by(sum_map) == result }
    combinations.uniq
  end
end

p GuessAddition::guess_this("15112", 28) # => [[15, 1, 12], [15, 11, 2]]

Answer 2

Идея состоит в том, чтобы использовать динамическое программирование, вы заботитесь только о суммах от 0 до 10 ^ 6 и имеете только 120 возможных индексов.если dp [i] [j] = x, это означает, что из индекса x строки мы перешли к индексу i (поэтому мы добавили + перед i) и получили сумму j.Это приводит к решению O (| S | * N):

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string s;
long n;

long dp[123][1000001];

void solve (int index, long sum) {//index = what index of s still remains to scan. sum = the sum we have accumulated till now
    if (sum >= n or index >= s.length()) return;
    if (dp[index][sum] != -1) return;
    if (index == n and sum == n) return;

    long num = 0;

    for (int i = 0; i < 7 && index + i < s.length(); i++) { //N has 6 digits at most
        num = stoi(s.substr(index, i + 1)); 
        solve(index + i + 1, sum + num); 
        if (sum + num <= n) {
            dp[index + i + 1][sum + num] = index;
        }
    }

}

int main () {
    cin >> s;
    cin >> n;

    for (int i = 0; i < 121; i++) {
        for (int j = 0; j < 1000001; j++) {
            dp[i][j] = -1;
        }
    }

    solve(0, 0);

    int sum = n;
    int idx = s.length();

    vector<string> nums;
    //reconstruct solution
    while (idx != 0) {
        nums.push_back(s.substr(dp[idx][sum], idx - dp[idx][sum])); 
        idx = dp[idx][sum];
        sum -= stoi(nums[nums.size() - 1]);
    }

    for (int i = nums.size() -1; i >= 0; i--) {
        cout << nums[i];
        if (i != 0) cout << "+";
    }

}

Answer 3

Могут быть более эффективные способы сделать это, но так как у вас пока ничего нет ...

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

Например: при вводе 112134, 1 + 12 + 13 + 4 может быть представлен с логическим массивом [true, false, true, false, true], указывающим, что после 1-го, 3-го и 5-го чисел есть плюс.Затем проблема сводится к поиску, какие комбинации добавить к вашему номеру.Есть много способов найти комбинации.Рекурсивный возврат является классикой.

В javascript / node это может выглядеть так:

function splitOnIndexes(arr, a) {
  // split the array into numbers based on the booleans
  let current = "" + arr[0]
  let output = []
  for (let i = 0; i < a.length; i++) {
    if (!a[i]) {
      current += arr[i + 1]
    } else {
      output.push(current)
      current = "" + arr[i + 1]
    }
  }
  output.push(current)
  return output
}

function findSum(input, total) {
  function backtrack(n, k = 0, a = []) {
    const sum = (arr) => arr.reduce((a, c) => a + parseInt(c), 0)
    if (k === n) {
      let ans = splitOnIndexes(input, a)
      if (sum(ans) === total) {
        console.log(ans.join(' + '))
      }
    } else {
      k = k + 1
      let c = [true, false]
      for (let i = 0; i < 2; i++) {
        a[k - 1] = c[i]
        backtrack(n, k, a)
      }
    }
  }

  backtrack(input.length - 1)
}

findSum('15112', 28)

findSum('120012', 33)

findSum('123', 123)

Как видите, возможно более одного ответа.Ваш первый пример решен с 15+1+12 и 15+11+2.Если вам нужен только один, вы, конечно, можете остановиться рано.