Учитывая последовательность чисел и число операторов умножения, какое наибольшее число можно вычислить?

Ответ 1

Я предполагаю здесь, что требуемое число m операторов умножения задано как часть проблемы вместе с строкой s цифр.

Вы можете решить эту проблему, используя табличный метод (так называемое "динамическое программирование" ) с помощью O (m | s | ²) умножения чисел, которые O (| s |) цифры длинны. оптимальная вычислительная сложность умножения неизвестна, но с алгоритмом умножения учебника это O (m | s | ⁴) в целом.

(Идея состоит в том, чтобы вычислить ответ для каждой подзадачи, состоящей из хвоста строки и числа m '≤ m. Существуют такие подзадачи O (m | s |), и каждый из них включает O (| s | ) умножения чисел, которые являются O (| s |) длинными цифрами.)

В Python вы можете запрограммировать его так, используя @memoized decorator из библиотеки декораторов Python:

@memoized
def max_product(s, m):
    """Return the maximum product of digits from the string s using m
    multiplication operators.

    """
    if m == 0:
        return int(s)
    return max(int(s[:i]) * max_product(s[i:], m - 1)
               for i in range(1, len(s) - m + 1))

Если вы привыкли к восходящей форме динамического программирования, где вы создаете таблицу, эта форма сверху вниз может выглядеть странно, но на самом деле @memoized decorator поддерживает таблицу в свойстве cache функции:

>>> max_product('56789', 1)
51102
>>> max_product.cache
{('89', 0): 89, ('9', 0): 9, ('6789', 0): 6789, ('56789', 1): 51102, ('789', 0): 789}

Ответ 2

Версия java, хотя Python уже продемонстрировал свое функциональное преимущество и избил меня:

private static class Solution {
    BigInteger product;
    String expression;
}

private static Solution solve(String digits, int multiplications) {
    if (digits.length() < multiplications + 1) {
        return null; // No solutions
    }
    if (multiplications == 0) {
        Solution solution = new Solution();
        solution.product = new BigInteger(digits);
        solution.expression = digits;
        return solution;
    }
    // Position of first '*':
    Solution max = null;
    for (int i = 1; i < digits.length() - (multiplications - 1); ++i) {
        BigInteger n = new BigInteger(digits.substring(0, i));
        Solution solutionRest = solve(digits.substring(i), multiplications - 1);
        n = n.multiply(solutionRest.product);
        if (max == null || n.compareTo(max.product) > 0) {
            solutionRest.product = n;
            solutionRest.expression = digits.substring(0, i) + "*"
                + solutionRest.expression;
            max = solutionRest;
        }
    }
    return max;
}

private static void test(String digits, int multiplications) {
    Solution solution = solve(digits, multiplications);
    System.out.printf("%s %d -> %s = %s%n", digits, multiplications,
            solution.expression, solution.product.toString());
}

public static void main(String[] args) {
    test("1826456903521651", 5);
}

Выход

1826456903521651 5 -> 182*645*6*903*521*651 = 215719207032420

Ответ 3

Здесь итеративное решение динамического программирования.

В отличие от рекурсивной версии (которая должна иметь аналогичное время работы).

Основная идея:

A[position][count] - наибольшее число, которое можно получить, заканчивая в позиции position, используя count умножения.

Итак:

A[position][count] = max(for i = 0 to position
                           A[i][count-1] * input.substring(i, position))

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

Сложность:

Для строки |s| с m операторы умножения, которые нужно вставить...

O(m|s|2g(s)) где g(s) сложность умножения.

Java-код:

static long solve(String digits, int multiplications)
{
  if (multiplications == 0)
     return Long.parseLong(digits);

  // Preprocessing - set up substring values
  long[][] substrings = new long[digits.length()][digits.length()+1];
  for (int i = 0; i < digits.length(); i++)
  for (int j = i+1; j <= digits.length(); j++)
     substrings[i][j] = Long.parseLong(digits.substring(i, j));

  // Calculate multiplications from the left
  long[][] A = new long[digits.length()][multiplications+1];
  A[0][0] = 1;
  for (int i = 1; i < A.length; i++)
  {
     A[i][0] = substrings[0][i];
     for (int j = 1; j < A[0].length; j++)
     {
        long max = -1;
        for (int i2 = 0; i2 < i; i2++)
        {
           long l = substrings[i2][i];
           long prod = l * A[i2][j-1];
           max = Math.max(max, prod);
        }
        A[i][j] = max;
     }
  }

  // Multiply left with right and find maximum
  long max = -1;
  for (int i = 1; i < A.length; i++)
  {
     max = Math.max(max, substrings[i][A.length] * A[i][multiplications]);
  }
  return max;
}

Очень простой тест:

System.out.println(solve("99287", 1));
System.out.println(solve("99287", 2));
System.out.println(solve("312", 1));

Печать

86304
72036
62

Да, он просто печатает максимум. Это не слишком сложно, чтобы на самом деле распечатать суммы, если это необходимо.

Ответ 4

здесь другое решение Java. (Я знаю, что это правильно для "312" и 1 умножения, и я думаю, что это работает для других...

Вам нужно будет запомнить, как получить сложность рекурсивных методов самостоятельно, ха-ха.

package test;

import java.util.ArrayList;
import java.util.List;

public class BiggestNumberMultiply {

    private static class NumberSplit{
        String[] numbers;
        long result;
        NumberSplit(String[] numbers){
            this.numbers=numbers.clone();
            result=1;
            for(String n:numbers){
                result*=Integer.parseInt(n);
            }
        }
        @Override
        public String toString() {
            StringBuffer sb=new StringBuffer();
            for(String n:numbers){
                sb.append(n).append("*");
            }
            sb.replace(sb.length()-1, sb.length(), "=")
                .append(result);
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        String numbers = "312";
        int numMults=1;

        int numSplits=numMults;

        List<NumberSplit> splits = new ArrayList<NumberSplit>();
        splitNumbersRecursive(splits, new String[numSplits+1], numbers, numSplits);
        NumberSplit maxSplit = splits.get(0);
        for(NumberSplit ns:splits){
            System.out.println(ns);
            if(ns.result>maxSplit.result){
                maxSplit = ns;
            }
        }
        System.out.println("The maximum is "+maxSplit);
    }

    private static void splitNumbersRecursive(List<NumberSplit> list, String[] splits, String numbers, int numSplits){
        if(numSplits==0){
            splits[splits.length-1] = numbers;
            return;
        }
        for(int i=1; i<=numbers.length()-numSplits; i++){
            splits[splits.length-numSplits-1] = numbers.substring(0,i);
            splitNumbersRecursive(list, splits, numbers.substring(i), numSplits-1);
            list.add(new NumberSplit(splits));
        }
    }
}

Ответ 5

Еще одна реализация Java. Это DP сверху вниз, ака memoization. Он также распечатывает фактические компоненты, кроме максимального продукта.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MaxProduct {

    private static Map<Key, Result> cache = new HashMap<>();

    private static class Key {
        int operators;
        int offset;

        Key(int operators, int offset) {
            this.operators = operators;
            this.offset = offset;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + offset;
            result = prime * result + operators;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (!(obj instanceof Key)) {
                return false;
            }
            Key other = (Key) obj;
            if (offset != other.offset) {
                return false;
            }
            if (operators != other.operators) {
                return false;
            }
            return true;
        }
    }

    private static class Result {
        long product;
        int offset;
        Result prev;

        Result (long product, int offset) {
            this.product = product;
            this.offset = offset;
        }

        @Override
        public String toString() {
            return "product: " + product + ", offset: " + offset;
        }
    }

    private static void print(Result result, String input, int operators) {
        System.out.println(operators + " multiplications on: " + input);
        Result current = result;
        System.out.print("Max product: " + result.product + " = ");
        List<Integer> insertions = new ArrayList<>();
        while (current.prev != null) {
            insertions.add(current.offset);
            current = current.prev;
        }

        List<Character> inputAsList = new ArrayList<>();
        for (char c : input.toCharArray()) {
            inputAsList.add(c);
        }

        int shiftedIndex = 0;
        for (int insertion : insertions) {
            inputAsList.add(insertion + (shiftedIndex++), '*');
        }

        StringBuilder sb = new StringBuilder();
        for (char c : inputAsList) {
            sb.append(c);
        }

        System.out.println(sb.toString());
        System.out.println("-----------");
    }

    public static void solve(int operators, String input) {
        cache.clear();
        Result result = maxProduct(operators, 0, input);
        print(result, input, operators);
    }

    private static Result maxProduct(int operators, int offset, String input) {
        String rightSubstring = input.substring(offset);

        if (operators == 0 && rightSubstring.length() > 0) return new Result(Long.parseLong(rightSubstring), offset);
        if (operators == 0 && rightSubstring.length() == 0) return new Result(1, input.length() - 1);

        long possibleSlotsForFirstOperator = rightSubstring.length() - operators;
        if (possibleSlotsForFirstOperator < 1) throw new IllegalArgumentException("too many operators");

        Result maxProduct = new Result(-1, -1);
        for (int slot = 1; slot <= possibleSlotsForFirstOperator; slot++) {
            long leftOperand = Long.parseLong(rightSubstring.substring(0, slot));
            Result rightOperand;
            Key key = new Key(operators - 1, offset + slot);
            if (cache.containsKey(key)) {
                rightOperand = cache.get(key);
            } else {
                rightOperand = maxProduct(operators - 1, offset + slot, input);
            }

            long newProduct = leftOperand * rightOperand.product;
            if (newProduct > maxProduct.product) {
                maxProduct.product = newProduct;
                maxProduct.offset = offset + slot;
                maxProduct.prev = rightOperand;
            }
        }

        cache.put(new Key(operators, offset), maxProduct);
        return maxProduct;
    }

    public static void main(String[] args) {
        solve(5, "1826456903521651");
        solve(1, "56789");
        solve(1, "99287");
        solve(2, "99287");
        solve(2, "312");
        solve(1, "312");
    }

}

Бонус: исполнение для брутфорса для всех, кого это интересует. Не особенно умно, но делает шаг трассировки простым.

import java.util.ArrayList;
import java.util.List;

public class MaxProductBruteForce {

    private static void recurse(boolean[] state, int pointer, int items, List<boolean[]> states) {
        if (items == 0) {
            states.add(state.clone());
            return;
        }

        for (int index = pointer; index < state.length; index++) {
            state[index] = true;
            recurse(state, index + 1, items - 1, states);
            state[index] = false;
        }
    }

    private static List<boolean[]> bruteForceCombinations(int slots, int items) {
        List<boolean[]> states = new ArrayList<>(); //essentially locations to insert a * operator
        recurse(new boolean[slots], 0, items, states);
        return states;
    }

    private static class Tuple {
        long product;
        List<Long> terms;

        Tuple(long product, List<Long> terms) {
            this.product = product;
            this.terms = terms;
        }

        @Override
        public String toString() {
            return product + " = " + terms.toString();
        }
    }

    private static void print(String input, int operators, Tuple result) {
        System.out.println(operators + " multiplications on: " + input);
        System.out.println(result.toString());
        System.out.println("---------------");
    }

    public static void solve(int operators, String input) {
        Tuple result = maxProduct(input, operators);
        print(input, operators, result);
    }

    public static Tuple maxProduct(String input, int operators) {
        Tuple maxProduct = new Tuple(-1, null);

        for (boolean[] state : bruteForceCombinations(input.length() - 1, operators)) {
            Tuple newProduct = getProduct(state, input);
            if (maxProduct.product < newProduct.product) {
                maxProduct = newProduct;
            }
        }

        return maxProduct;
    }

    private static Tuple getProduct(boolean[] state, String input) {
        List<Long> terms = new ArrayList<>();
        List<Integer> insertLocations = new ArrayList<>();
        for (int i = 0; i < state.length; i++) {
            if (state[i]) insertLocations.add(i + 1);
        }

        int prevInsert = 0;
        for (int insertLocation : insertLocations) {
            terms.add(Long.parseLong(input.substring(prevInsert, insertLocation))); //gradually chop off the string
            prevInsert = insertLocation;
        }

        terms.add(Long.parseLong(input.substring(prevInsert))); //remaining of string

        long product = 1;
        for (long term : terms) {
            product = product * term;
        }

        return new Tuple(product, terms);
    }

    public static void main(String[] args) {
        solve(5, "1826456903521651");
        solve(1, "56789");
        solve(1, "99287");
        solve(2, "99287");
        solve(2, "312");
        solve(1, "312");
    }

}

Ответ 6

Эта реализация предназначена для @lars.

from __future__ import (print_function)
import collections
import sys

try:
    xrange
except NameError:  # python3
    xrange = range


def max_product(s, n):
    """Return the maximum product of digits from the string s using m
    multiplication operators.

    """
    # Guard condition.
    if len(s) <= n:
        return None

    # A type for our partial solutions.
    partial_solution = collections.namedtuple("product",
                                              ["value", "expression"])

    # Initialize the best_answers dictionary with the leading terms
    best_answers = {}
    for i in xrange(len(s)):
        term = s[0: i+1]
        best_answers[i+1] = partial_solution(int(term), term)

    # We then replace best_answers n times.
    for prev_product_count in [x for x in xrange(n)]:
        product_count = prev_product_count + 1
        old_best_answers = best_answers
        best_answers = {}
        # For each position, find the best answer with the last * there.
        for position in xrange(product_count+1, len(s)+1):
            candidates = []
            for old_position in xrange(product_count, position):
                prior_product = old_best_answers[old_position]
                term = s[old_position:position]
                value = prior_product.value * int(term)
                expression = prior_product.expression + "*" + term
                candidates.append(partial_solution(value, expression))
            # max will choose the biggest value, breaking ties by the expression
            best_answers[position] = max(candidates)

    # We want the answer with the next * going at the end of the string.
    return best_answers[len(s)]

print(max_product(sys.argv[1], int(sys.argv[2])))

Вот примерный прогон:

$ python mult.py 99287 2
product(value=72036, expression='9*92*87')

Надеюсь, логика понятна из реализации.

Ответ 7

Я нашел, что вышеупомянутое решение DP полезно, но запутывает. Повторение имеет смысл, но я хотел сделать все это за один стол без этой окончательной проверки. Мне потребовались годы, чтобы отладить все индексы, поэтому я объяснял несколько слов.

Напомним:

• Инициализировать T с размером N (потому что цифры 0..N-1) на k + 1 (потому что умножения 0..k).
• Таблица T (i, j) = максимально возможное произведение с использованием первых цифр я + 1 строки (из-за нулевой индексации) и j-умножений.
• Базовый регистр: T (i, 0) = цифры [0..i] для я в 0..N-1.
• Повторяемость: T (i, j) = max _a (T (a, j-1) * цифры [a + 1..i]). То есть: цифры раздела [0..i] в цифрах [0..a] * цифры [a + 1..i]. И поскольку это связано с умножением, подзадача имеет меньшее количество умножений, поэтому выполните поиск в таблице в j-1.
• В конце ответ сохраняется в T (все цифры, все умножения) или T (N-1, k).

Сложность O (N ² k), поскольку максимизация над a равна O (N), и мы делаем это O (k) раз для каждой цифры (O (N)).

public class MaxProduct {

    public static void main(String ... args) {
        System.out.println(solve(args[0], Integer.parseInt(args[1])));
    }

    static long solve(String digits, int k) {
        if (k == 0)
            return Long.parseLong(digits);

        int N = digits.length();
        long[][] T = new long[N][k+1];
        for (int i = 0; i < N; i++) {
            T[i][0] = Long.parseLong(digits.substring(0,i+1));
            for (int j = 1; j <= Math.min(k,i); j++) {
                long max = Integer.MIN_VALUE;
                for (int a = 0; a < i; a++) {
                    long l = Long.parseLong(digits.substring(a+1,i+1));
                    long prod = l * T[a][j-1];
                    max = Math.max(max, prod);
                }
                T[i][j] = max;
            }
        }
        return T[N-1][k];
    }
}

Ответ 8

Это напомнило, что подход грубой силы зависит от проблемы баров и звезд.

Скажем, наш номер "12345" и у нас есть 2 * -операторы, которые нам нужно использовать. Мы можем посмотреть на строку 12345 как

1_2_3_4_5

Где мы можем поместить два оператора * на любое из подчеркиваний. Так как есть 4 символа подчеркивания и 2 *, есть 4 варианта 2 (или 6) разных способов размещения операторов. Сравните эти 6 возможностей и получите наибольшее количество. Аналогичный подход можно использовать для больших строк и большего числа операторов *.

Ответ 9

Я уверен, что ответ состоит в том, чтобы просто поставить * прямо перед самыми большими цифрами, так что наибольшая цифра имеет наибольшее влияние. Например, если мы имеем

 1826456903521651 

и у нас есть пять умножений, это будет ответ.

 1*82*645*6*903521*651 

Таким образом, время работы будет линейным.

Изменить: Хорошо, так что это неправильно. У нас есть два контрпримера.