Алгоритм для поиска целевой суммы суммы произведений двух списков упорядоченных целых чисел

Question

Я работаю, пытаясь написать сценарий для синтаксического анализа слабо преобразованных таблиц в текстовой форме, которая исходит из разбора pdf: s в csv: s. По существу заголовки - это длины досок, данные - количество досок, и, наконец, дается общая длина всех досок в ряду.

Упрощенный пример

1,0 2,0 3,0 4,0 5,0 total M 
1  3 2  1   17,0 

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

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

Правила этой проблемы с игрушкой тогда.

Два списка целых чисел, первые [1..14], второстепенные мелкие целые числа (< 1000) и от 1 до 14 членов. называть их длины и numPlanks

Целевая сумма, которая определяется суммированием продуктов всех членов numPlanks с ровно одним членом длин и без двух членов numPlanks, может делиться длиной. Поиск по всем таким комбинациям и печать комбинаций, соответствующих цели.

Далее, члены обоих списков упорядочены. Если первый элемент numPlanks умножается на второй элемент длин, ни один другой член numPlanks не может быть умножен на первый элемент длин.

Пример, в псевдокоде

lengths = [1, 2, 3, 4] 
numPlanks = [10, 20] 
target = 110 

программа будет затем проверить 10 + 40, 10 + 60, 10 + 80, 20 + 60, 20 + 80, 30 + 80, чтобы увидеть, которые складываются к цели и, наконец, распечатать что-то вроде «10 * 30 + 20 * 40 = 110».

Я пытался создать решения, но я был в тупике, только имея возможность думать о вложении столько циклов, сколько есть членов в numPlanks. Что кажется ужасным.

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

Редактировать: эскиз с ручкой и бумагой кажется, что количество сравнений связано с треугольником Паскаля. Например, для длин с двумя членами и numPlacks с 0 до 2 членами число сравнений равно 1,2,1 для 0, 1 и 2 членов в numPlanks соответственно.

Учитывая, что я знаю, что у меня ровно 14 членов в моей реальной проблеме и от 1 до 14 членов в numPlanks, это будет соответствовать худшему случаю 1716 сравнений. Кажется, все в порядке.

Answer 1

Короткий ответ: ваша оценка количества вычислений безнадежно оптимистична, если только я не понимаю вашу проблему.

Предположим, у вас есть 14 элементов в lengths и 14 элементах в numPlanks.Поскольку каждая длина и каждый numPlank могут использоваться только один раз (если я правильно понимаю), тогда у вас в основном есть 14 * 14 = 196 возможных терминов, и вам нужно найти некоторую комбинацию из них, которая соответствует вашей цели.

Предположим, вы начинаете с предположения, что решение включает определенную длину и определенные numPlanks. Это означает, что вы можете перечеркнуть 13 других терминов, имеющих одинаковые numPlanks, как ваша догадка, и 13 других терминов, имеющих ту же длину, что и ваша догадка. И, конечно же, вы можете перечеркнуть тот термин, который вы догадались. Это все еще оставляет вам 169 терминов, чтобы попытаться добавить к этому предположению.

Итак, вы выбираете. Теперь вы перечеркиваете 12 + 13 терминов, как раньше, потому что они разделяют ценность с вашей догадкой на 2-й срок. Теперь у вас осталось 144 слова ... и т. Д.

Итак, чтобы получить все возможные догадки из трех терминов, вы должны посмотреть на 196 * 169 * 144 = 4,7 миллиона возможностей.

Вот код Java, который генерирует решения. Эта версия имеет 14 элементов в каждом массиве. Он находит решение после 64000 сравнений (намного выше, чем ваша худшая оценка). Если вы даете ему что-то неразрешимой (например, сделать все число длин делится на 10 и дать ему цель 2051), а затем пойти получить чашку кофе и ждать вселенной до конца ...

public class Tester { 

    static int numComparisons = 0; 

    public static class Term { 
     final int length; 
     final int numPlanks; 

     public Term(final int length, final int numPlanks) { 
      this.length = length; 
      this.numPlanks = numPlanks; 
     } 

     @Override 
     public String toString() { 
      return "(" + this.length + "*" + this.numPlanks + ")"; 
     } 
    } 

    public static List<Term> getTerms(int target, List<Integer> lengthsList, 
      List<Integer> numPlanksList, List<Term> currentTermList) { 
     // System.out.println("... " + target + ", " + lengthsList + ", " + 
     // numPlanksList + ", " + currentTermList); 
     lengthsLoop: for (int l : lengthsList) { 
      numPlanksLoop: for (int n : numPlanksList) { 
       numComparisons++; 
       if (numComparisons % 100 == 0) { 
        System.out.println("... numComparisons = " + numComparisons 
          + " .... " + currentTermList); 
       } 
       if ((l * n) > target) { 
        continue lengthsLoop; 
       } else if (l * n == target) { 
        final List<Term> newCurrentTermList = new ArrayList<Term>(
          currentTermList); 
        newCurrentTermList.add(new Term(l, n)); 
        return newCurrentTermList; 
       } else { 
        final int newTarget = target - (l * n); 
        final List<Integer> newLengthsList = new ArrayList<Integer>(
          lengthsList); 
        newLengthsList.remove((Integer) l); 
        final List<Integer> newNumPlanksList = new ArrayList<Integer>(
          numPlanksList); 
        newNumPlanksList.remove((Integer) n); 
        final List<Term> newCurrentTermList = new ArrayList<Term>(
          currentTermList); 
        newCurrentTermList.add(new Term(l, n)); 
        final List<Term> answer = getTerms(newTarget, 
          newLengthsList, newNumPlanksList, 
          newCurrentTermList); 
        if (answer.size() > 0) { 
         return answer; 
        } 
       } 
      } 
     } 

     // System.out.println("Over!"); 
     return new ArrayList<Term>(); 

    } 

    public static void main(String[] args) { 

     List<Integer> lengthsList = new ArrayList<Integer>(Arrays.asList(1, 2, 
       3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)); 
     Collections.sort(lengthsList, Collections.reverseOrder()); 
     List<Integer> numPlanksList = new ArrayList<Integer>(Arrays.asList(1, 
       20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140)); 
     Collections.sort(numPlanksList, Collections.reverseOrder()); 
     int target = 2051; 

     final List<Term> finalAnswer = getTerms(target, lengthsList, 
       numPlanksList, new ArrayList<Term>()); 
     if (finalAnswer.size() > 0) { 
      System.out.println("Final Answer:"); 
      System.out.println("============="); 
      for (Term t : finalAnswer) { 
       System.out.println(t.length + "*" + t.numPlanks); 
      } 
     } else { 
      System.out.println("No solution"); 
     } 
     System.out.println("numComparisons = " + numComparisons); 

    } 
} 

Answer 2

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

Тестирование с

int[] lengths = { 1, 2, 3, 4 }; 
    int[] plankCount = { 10, 20 }; 
    int totalPlankLength = 110; 

я получил следующий результат:

[10 x 3, 20 x 4] 

Тестирование с

int[] lengths = { 1, 2, 3, 4, 5, 6, 7 }; 
    int[] plankCount = { 10, 20, 30 }; 
    int totalPlankLength = 280; 

Я получил следующие результаты

[10 x 1, 20 x 3, 30 x 7] 
    [10 x 2, 20 x 4, 30 x 6] 

Благодаря greybeard для комментария. В приведенном примере, скорее всего, подходит более одного ответа. С реальными данными это менее вероятно, но все же возможно.

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

Позвольте мне проиллюстрировать более простой пример. Мы имеем следующий вход:

int[] lengths = { 1, 2, 3, 4 }; 
    int[] plankCount = { 10, 20 }; 
    int totalPlankLength = 110; 

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

Во-первых, я вычислил количество возможностей, вычислив 2 на длину длины. В этом примере мы вычисляем 2 на 4-ю степень или 16.

Поскольку мы используем int, максимальная длина списка длин равна 30. Если вам нужен более длинный список, вам нужно будет преобразовать ints к longs.

Нам не нужно смотреть на все двоичные числа от 15 до 0. Нам просто нужно посмотреть на двоичные числа, у которых длина доски равна одной бит. Мы смотрим на двоичные числа в обратном порядке.

12 1100 
10 1010 
9 1001 
6 0110 
5 0101 
3 0011 

Десятичные числа слева не имеют значения. Правило бит - это то, что важно. Набор битовых шаблонов показывает количество способов умножения plankCount на длину.

Итак, мы будем выполнять 6 умножений с двумя подсчетами досок, в общей сложности 12 умножений. Это происходит быстро.

Я делаю умножения и суммирую продукты для каждого бинарного паттерна, чтобы увидеть, равна ли сумма общей длине доски. Если это так, я пишу эти умножения.

Вот исправленный код. Попробуйте это с длиной 14 и посмотрите, достаточно ли это для ваших нужд.

package com.ggl.testing; 

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

public class BoardLength { 

    public static void main(String[] args) { 
     BoardLength boardLength = new BoardLength(); 
     int[] lengths = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
     int[] plankCount = { 10, 20, 30 }; 
     int totalPlankLength = 360; 
     List<List<PlankLength>> plankLength = boardLength.calculatePlankLength(
       lengths, plankCount, totalPlankLength); 
     displayResults(plankLength); 
    } 

    private static void displayResults(List<List<PlankLength>> plankLength) { 
     if (plankLength.size() <= 0) { 
      System.out.println("[]"); 
     } else { 
      for (List<PlankLength> list : plankLength) { 
       System.out.println(Arrays.toString(list.toArray())); 
      } 
     } 
    } 

    public List<List<PlankLength>> calculatePlankLength(int[] lengths, 
      int[] plankCount, int totalPlankLength) { 
     List<List<PlankLength>> plankLength = new ArrayList<>(); 
     String formatString = "%" + lengths.length + "s"; 

     int maximum = (int) Math.round(Math.pow(2D, (double) lengths.length)); 
     for (int index = maximum - 1; index >= 0; index--) { 
      int bitCount = Integer.bitCount(index); 
      if (bitCount == plankCount.length) { 
       String bitString = String.format(formatString, 
         Integer.toBinaryString(index)).replace(' ', '0'); 
       calculateTotalPlankLength(lengths, plankCount, 
         totalPlankLength, plankLength, bitString); 
      } 
     } 

     return plankLength; 
    } 

    private void calculateTotalPlankLength(int[] lengths, int[] plankCount, 
      int totalPlankLength, List<List<PlankLength>> plankLength, 
      String bitString) { 
     List<PlankLength> tempList = new ArrayList<>(); 
     int plankIndex = 0; 
     int sum = 0; 
     for (int bitIndex = 0; bitIndex < bitString.length(); bitIndex++) { 
      if (bitString.charAt(bitIndex) == '1') { 
       PlankLength pl = new PlankLength(lengths[bitIndex], 
         plankCount[plankIndex++]); 
       sum += pl.getPlankLength(); 
       tempList.add(pl); 
      } 
     } 

     if (sum == totalPlankLength) { 
      plankLength.add(tempList); 
     } 
    } 

    public class PlankLength { 
     private final int length; 
     private final int plankCount; 

     public PlankLength(int length, int plankCount) { 
      this.length = length; 
      this.plankCount = plankCount; 
     } 

     public int getLength() { 
      return length; 
     } 

     public int getPlankCount() { 
      return plankCount; 
     } 

     public int getPlankLength() { 
      return length * plankCount; 
     } 

     @Override 
     public String toString() { 
      return "" + plankCount + " x " + length; 
     } 

    } 

}