Существуют ли какие-либо "трюки", чтобы ускорить выборку очень сложного типа комбинаций рюкзаков?

ОБНОВЛЕНИЕ: я понял, что нижеприведенная проблема не может отвечать в ее текущей форме из-за большого количества данных (15k + items). Я только что узнал, группа, которую я пытаюсь помочь, просто запускает ее на месяц, а затем завершает ее, чтобы использовать результаты (вот почему они хотели получить больше результатов быстрее). Мне это кажется безумным, потому что они используют только первые несколько наборов данных (последние элементы в больших списках никогда не используются). Поэтому я пересматриваю этот вопрос, чтобы получить образец предполагаемого вывода (аппроксимация решений не является полным решением). Какой лучший способ завершить это за меньшее количество времени? Кажется, они хотят получить разнообразную выборку результатов, работают ли генетические алгоритмы или какой-то метод отбора проб? Остальная часть вопроса остается той же (одни и те же входы/выходы), но я не ищу полного решения, установленного сейчас (поскольку оно никогда не будет завершено за всю жизнь, но я надеюсь, что будет иметься список со множеством разнообразных решений).

Моя проблема не совсем проблема с рюкзаком, но ее довольно близко. В основном, я пытаюсь найти каждую комбинацию элементов X, которые равны определенному значению. Я слышал об этой проблеме от моего друга, который работал в небольшой научной исследовательской лаборатории, где этот процесс был запущен и занял около 25 дней. Мне показалось действительно ужасным, поэтому я предложил помочь (мне полезно, я узнаю и помогу некоторым действительно приятным людям), поэтому я выяснил, как масштабировать его путем многопоточности (я включу код ниже), это вырезали несколько дней с момента их обработки, но я все еще не был удовлетворен, поэтому я просто портировал свой код для работы на графическом процессоре, но я не чувствую себя удовлетворенным (хотя они счастливы, потому что быстрее, и я пожертвовал свою старую видеокарту), потому что Я просто использую аппаратное обеспечение, а не алгоритмы. Прямо сейчас, я просто грубо заставляю результаты, проверяя, равно ли значение, равное сумме, и если оно делает, то сохраняет результат, если он не продолжает его обрабатывать.

Итак, с этим фоном, я могу что-то сделать, чтобы ускорить его алгоритмически? Моя кишка говорит мне нет, потому что, поскольку им нужна каждая комбинация, логически кажется, что компьютер должен обрабатывать каждую комбинацию (это несколько миллиардов), но я видел здесь удивительные вещи, и даже небольшое ускорение может изменить ситуацию в дни обработки.

У меня есть более 10 версий кода, но здесь версия Java, использующая многопоточность (но логика между этим и gpu почти одинакова).

Базовая логика:

for (int c = 100; c >= 0; c--) {
    if (c * x_k == current.sum) { //if result is correct then save
        solutions.add(new Context(0, 0, newcoeff));
        continue;
     } else if (current.k > 0) { //if result is not equal but not end of list then send to queue
         contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff));
     }
 }

Полный код:

import java.util.Arrays;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class MixedParallel
{
    // pre-requisite: sorted values !!
    private static final int[] data = new int[] { -5,10,20,30,35 };

    // Context to store intermediate computation or a solution
    static class Context {
        int k;
        int sum;
        int[] coeff;
        Context(int k, int sum, int[] coeff) {
            this.k = k;
            this.sum = sum;
            this.coeff = coeff;
        }
    }

    // Thread pool for parallel execution
    private static ExecutorService executor;
    // Queue to collect solutions
    private static Queue<Context> solutions;

    static {
        final int numberOfThreads = 2;
        executor =
            new ThreadPoolExecutor(numberOfThreads, numberOfThreads, 1000, TimeUnit.SECONDS,
                                   new LinkedBlockingDeque<Runnable>());
        // concurrent because of multi-threaded insertions
        solutions = new ConcurrentLinkedQueue<Context>();
    }


    public static void main(String[] args)
    {
        System.out.println("starting..");
        int target_sum = 100;
        // result vector, init to 0
        int[] coeff = new int[data.length];
        Arrays.fill(coeff, 0);
        mixedPartialSum(data.length - 1, target_sum, coeff);

        executor.shutdown();
        // System.out.println("Over. Dumping results");
        while(!solutions.isEmpty()) {
            Context s = solutions.poll();
            printResult(s.coeff);
        }
    }

    private static void printResult(int[] coeff) {
        StringBuffer sb = new StringBuffer();
        for (int i = coeff.length - 1; i >= 0; i--) {
            if (coeff[i] > 0) {
                sb.append(data[i]).append(" * ").append(coeff[i]).append(" + ");
            }
        }
        System.out.println(sb);
    }

    private static void mixedPartialSum(int k, int sum, int[] coeff) {
        int x_k = data[k];
        for (int c = 0; c <= 100; c++) {
            coeff[k] = c;
            int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
            if (c * x_k == sum) {
                //printResult(newcoeff);
                solutions.add(new Context(0, 0, newcoeff));
                continue;
            } else if (k > 0) {
                if (data.length - k < 2) {
                    mixedPartialSum(k - 1, sum - c * x_k, newcoeff);
                    // for loop on "c" goes on with previous coeff content
                } else {
                    // no longer recursive. delegate to thread pool
                    executor.submit(new ComputePartialSum(new Context(k - 1, sum - c * x_k, newcoeff)));
                }
            }
        }
    }

    static class ComputePartialSum implements Callable<Void> {
        // queue with contexts to process
        private Queue<Context> contexts;

        ComputePartialSum(Context request) {
            contexts = new ArrayDeque<Context>();
            contexts.add(request);
        }

        public Void call() {
            while(!contexts.isEmpty()) {
                Context current = contexts.poll();
                int x_k = data[current.k];
                for (int c = 0; c <= 100; c++) {
                    current.coeff[current.k] = c;
                    int[] newcoeff = Arrays.copyOf(current.coeff, current.coeff.length);
                    if (c * x_k == current.sum) {
                        //printResult(newcoeff);
                        solutions.add(new Context(0, 0, newcoeff));
                        continue;
                    } else if (current.k > 0) {
                        contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff));
                    }
                }
            }
            return null;
        }
    }
}

Вот некоторые из характеристик данных/подхода:

Все номера являются шортами (число, похоже, не превышает +/- 200)
Существуют дубликаты (но не нулевые значения)
Цикл for ограничивает коэффициенты до 100 (это жесткое число и сказал, что это не изменится). Это ограничивает результаты
Существует предел количества элементов, но его переменная и определяется моя лаборатория друзей. Я тестировал с помощью двух пар, но мой друг сказал мне, что они используют 30-35 пар (это не комбинации, которые включают весь набор данных). Это также ограничивает результаты из-за отсутствия контроля.
Мой друг упомянул, что обработка сообщений, которую они выполняют, включает удаление всех результатов, которые содержат менее 30 коэффициентов, или более 35. В моем текущем коде я сломаю, если переменная newcoeff превышает число (в данном случае 35), но, возможно, там способ даже не обрабатывать результаты, которые ниже 30. Это может быть большой областью для сокращения времени обработки. поскольку теперь кажется, что они генерируют много бесполезных данных, чтобы добраться до тех, которые они хотят.
Их набор данных составляет 10k-15k элементов (отрицательный/положительный)
Я получаю только 3 элемента, два списка (один и один идентификационный номер идентифицировать данные) и целевую сумму. Затем я сохраняю файл со всеми комбинации данных в этом списке.
Я предложил помочь здесь, потому что эта часть заняла самое длинное время, прежде чем данные придут ко мне, они что-то делают (хотя они и делают не генерировать сами данные), и как только я отправлю им файл, они применять к ним свою собственную логику и обрабатывать ее. Таким образом, мой единственный фокус взяв 3 входа и создав выходной файл.
Использование потоков и графического процессора уменьшило проблему, чтобы неделя, но то, что я ищу здесь, - это идеи для улучшения алгоритма поэтому я могу использовать программное обеспечение вместо простого аппаратного gpus для увеличить скорость. Как видно из кода, его просто грубая сила прямо сейчас. Поэтому в идеале я бы хотел, чтобы предложения были потоковыми.

Update2: Я думаю, что проблема сама по себе довольно проста/распространена, но проблема запускается в масштабе, поэтому здесь реальные данные, которые я получил, когда мы проводили тест (его не так много, как у него, но его около 3000 элементов, поэтому, если вы хотите проверить, что вам не нужно его самостоятельно создавать):

private static final int target_sum = 5 * 1000;
private static final List<Integer> data = Arrays.asList( -193, -138, -92, -80, -77, -70, -63, -61, -60, -56, -56, -55, -54, -54, -51, -50, -50, -50, -49, -49, -48, -46, -45, -44, -43, -43, -42, -42, -42, -42, -41, -41, -40, -40, -39, -38, -38, -38, -37, -37, -37, -37, -37, -36, -36, -36, -35, -34, -34, -34, -34, -34, -34, -34, -33, -33, -33, -32, -32, -32, -32, -32, -32, -32, -32, -31, -31, -31, -31, -31, -31, -31, -30, -30, -30, -30, -30, -29, -29, -29, -29, -29, -29, -29, -29, -29, -28, -28, -28, -28, -27, -27, -27, -27, -26, -26, -26, -26, -26, -26, -25, -25, -25, -25, -25, -25, -25, -25, -24, -24, -24, -24, -24, -24, -24, -24, -24, -24, -23, -23, -23, -23, -23, -23, -23, -23, -22, -22, -22, -22, -22, -22, -22, -22, -22, -21, -21, -21, -21, -21, -21, -21, -20, -20, -20, -20, -20, -20, -20, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 36, 36, 36, 36, 37, 37, 38, 39, 39, 39, 40, 41, 41, 41, 41, 41, 42, 42, 43, 43, 44, 45, 45, 46, 47, 47, 48, 48, 49, 49, 50, 54, 54, 54, 55, 55, 56, 56, 57, 57, 57, 57, 57, 58, 58, 58, 59, 60, 66, 67, 68, 70, 72, 73, 73, 84, 84, 86, 92, 98, 99, 105, 114, 118, 120, 121, 125, 156);

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

Спасибо!

Ответ 1

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

public class TurboAdder {
    private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 };

    private static class Node {
        public final int index;
        public final int count;
        public final Node prevInList;
        public final int prevSum;
        public Node(int index, int count, Node prevInList, int prevSum) {
            this.index = index;
            this.count = count;
            this.prevInList = prevInList;
            this.prevSum = prevSum;
        }
    }

    private static int target = 100;
    private static Node sums[] = new Node[target+1];

    // Only for use by printString.
    private static boolean forbiddenValues[] = new boolean[data.length];

    public static void printString(String prev, Node n) {
        if (n == null) {
            System.out.println(prev);
        } else {
            while (n != null) {
                int idx = n.index;
                // We prevent recursion on a value already seen.
                if (!forbiddenValues[idx]) {
                    forbiddenValues[idx] = true;
                    printString((prev == null ? "" : (prev+" + "))+data[idx]+"*"+n.count, sums[n.prevSum]);
                    forbiddenValues[idx] = false;
                }
                n = n.prevInList;
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < data.length; i++) {
            int value = data[i];
            for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) {
                for (int newsum = sum+1; newsum <= target; newsum++) {
                    if (sums[newsum - sum] != null) {
                        sums[newsum] = new Node(i, count, sums[newsum], newsum - sum);
                    }
                }
            }
            for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) {
                sums[sum] = new Node(i, count, sums[sum], 0);
            }
        }
        printString(null, sums[target]);

    }
}

Ответ 2

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

Учитывая это, как только вы заполнили массив до длины N, вы заполняете запись N + 1, рассматривая каждый возможный элемент при каждой из 100 кратностей. Для каждого такого элемента вы вычитаете (кратность стоимости) из N + 1 и видите, что для получения общей стоимости N + 1 вы можете использовать этот элемент плюс любое решение для стоимости N + 1-thisCost. Таким образом, вы смотрите в массиве - назад на запись, которую вы уже заполнили, - чтобы увидеть, есть ли решение для N + 1-thisCost, и если да, и если текущая стоимость * кратность не меньше, чем какой-то элемент в массиве [N + 1-thisCost], вы можете добавить запись для элемента, кратность со смещением N + 1.

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

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

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

Ответ 3

Проблема, которую вы пытаетесь решить, называется разделение номера. Это особый случай проблемы с рюкзаком. Если значения являются целыми числами, и вы пытаетесь получить значение M, тогда вы можете найти одно решение в O (n * M) времени. Перечисление всех комбинаций может быть экспоненциальным, поскольку потенциально может быть экспоненциальное число решений.

Ответ 4

В приведенных данных приведены 137 уникальных значений (без учета повторов).

Если вы согласитесь, что почти любая комбинация из 30 различных значений, извлекаемых из данных случайным образом, может быть массирована по крайней мере в одном правильном решении путем корректировки коэффициентов, тогда должно быть не менее C (137,30) = 1,54E30 решений с ровно 30 членами (и еще 5.31E30 с 31 термином, 1.76E31 с 32 терминами, 5.60E31 с 33 терминами и т.д.).

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

Ниже приведена программа, которая применяет эту технику. На моем довольно скромном ноутбуке (1,3 ГГц AMD E-300) я выпустил 15000 уникальных решений за 2.249 секунд, нацеливая 32 члена на образец.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeMap;

public class ComboGen {

    private static final int[] data = { -193, -138, -92, -80, -77, -70, -63, -61, -60, -56, -56, -55, -54, -54, -51, -50, -50,
            -50, -49, -49, -48, -46, -45, -44, -43, -43, -42, -42, -42, -42, -41, -41, -40, -40, -39, -38, -38, -38, -37, -37,
            -37, -37, -37, -36, -36, -36, -35, -34, -34, -34, -34, -34, -34, -34, -33, -33, -33, -32, -32, -32, -32, -32, -32,
            -32, -32, -31, -31, -31, -31, -31, -31, -31, -30, -30, -30, -30, -30, -29, -29, -29, -29, -29, -29, -29, -29, -29,
            -28, -28, -28, -28, -27, -27, -27, -27, -26, -26, -26, -26, -26, -26, -25, -25, -25, -25, -25, -25, -25, -25, -24,
            -24, -24, -24, -24, -24, -24, -24, -24, -24, -23, -23, -23, -23, -23, -23, -23, -23, -22, -22, -22, -22, -22, -22,
            -22, -22, -22, -21, -21, -21, -21, -21, -21, -21, -20, -20, -20, -20, -20, -20, -20, -19, -19, -19, -19, -19, -19,
            -19, -19, -19, -19, -19, -19, -19, -19, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18,
            -18, -18, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -16, -16, -16, -16,
            -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15,
            -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -14, -14, -14, -14,
            -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -13, -13, -13, -13, -13, -13, -13,
            -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13,
            -13, -13, -13, -13, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12,
            -12, -12, -12, -12, -12, -12, -12, -12, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11,
            -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -10, -10, -10, -10, -10,
            -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10,
            -10, -10, -10, -10, -10, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9,
            -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9,
            -9, -9, -9, -9, -9, -9, -9, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8,
            -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -7,
            -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7,
            -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7,
            -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6,
            -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6,
            -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6,
            -6, -6, -6, -6, -6, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5,
            -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5,
            -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5,
            -5, -5, -5, -5, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4,
            -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4,
            -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4,
            -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4,
            -4, -4, -4, -4, -4, -4, -4, -4, -4, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3,
            -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3,
            -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3,
            -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3,
            -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -2, -2, -2, -2,
            -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,
            -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,
            -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,
            -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,
            -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1, -1,
            -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
            -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
            -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
            -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
            -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
            8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
            9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10,
            10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
            10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
            11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12,
            12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13,
            13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
            14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
            15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
            16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
            18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21,
            21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24,
            24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26,
            26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 30,
            30, 30, 31, 31, 31, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 36, 36, 36,
            36, 37, 37, 38, 39, 39, 39, 40, 41, 41, 41, 41, 41, 42, 42, 43, 43, 44, 45, 45, 46, 47, 47, 48, 48, 49, 49, 50, 54,
            54, 54, 55, 55, 56, 56, 57, 57, 57, 57, 57, 58, 58, 58, 59, 60, 66, 67, 68, 70, 72, 73, 73, 84, 84, 86, 92, 98, 99,
            105, 114, 118, 120, 121, 125, 156 };

    private static Map<Integer, Integer> buildCounts(int[] rawData) {
        Map<Integer, Integer> buckets = new TreeMap<Integer, Integer>();
        int i = 0;
        for (i = 0; i < rawData.length; i++) {
            if (buckets.containsKey(rawData[i])) {
                buckets.put(rawData[i], buckets.get(rawData[i]) + 1);
            } else {
                buckets.put(rawData[i], 1);
            }
        }
        weights = new int[buckets.size()];
        counts = new int[buckets.size()];
        i = 0;
        for (Entry<Integer, Integer> entry : buckets.entrySet()) {
            weights[i] = entry.getKey();
            counts[i] = entry.getValue();
            i++;
        }
        return buckets;
    }

    private static int[] weights;
    private static int[] counts;
    private static Random random = new Random(System.nanoTime());

    private static int[] placeChips(int[] chips, int targetPairs) {
        int unplaced = targetPairs;
        int[] placements = new int[unplaced];
        Arrays.fill(chips, 0);
        if (unplaced > chips.length) {
            throw new IllegalStateException("Coefficient pairs must not exceed unique data values.");
        }
        while (unplaced > 0) {
            int idx = random.nextInt(counts.length);
            if (chips[idx] == 0) {
                chips[idx] = 1 + random.nextInt(100);
                unplaced--;
            }
        }
        int ppos = 0;
        for (int cpos = 0; cpos < chips.length; cpos++) {
            if (chips[cpos] > 0) {
                placements[ppos++] = cpos;
            }
        }
        return placements;
    }

    static int sum(int[] chips) {
        int sum = 0;
        for (int i = 0; i < chips.length; i++) {
            sum += weights[i] * chips[i];
        }
        return sum;
    }

    public static void adjustFactors(int[] chips, int[] placements, int target) {
        int sum = sum(chips);
        Map<Integer, Integer> weightIdx = new HashMap<Integer, Integer>();
        for (int placement : placements) {
            weightIdx.put(weights[placement], placement);
        }
        while (sum != target) {
            // System.out.print(sum + ",");
            int idx = 0;
            if ((sum > target) && weightIdx.containsKey(sum - target) && (chips[weightIdx.get(sum - target)] > 1)) {
                idx = weightIdx.get(sum - target);
            } else if ((sum < target) && weightIdx.containsKey(sum - target) && (chips[weightIdx.get(sum - target)] > 1)) {
                idx = weightIdx.get(sum - target);
            } else if ((sum > target) && weightIdx.containsKey(target - sum) && chips[weightIdx.get(target - sum)] < 100) {
                idx = weightIdx.get(target - sum);
            } else if ((sum < target) && weightIdx.containsKey(target - sum) && chips[weightIdx.get(target - sum)] < 100) {
                idx = weightIdx.get(target - sum);
            } else {
                idx = placements[random.nextInt(placements.length)];
            }
            int weight = weights[idx];
            if (sum < target) {
                if (weight > 0 && chips[idx] < 100) {
                    chips[idx]++;
                    sum += weight;
                } else if (weight < 0 && chips[idx] > 1) {
                    chips[idx]--;
                    sum -= weight;
                }
            } else {
                if (weight > 0 && chips[idx] > 1) {
                    chips[idx]--;
                    sum -= weight;
                } else if (weight < 0 && chips[idx] < 100) {
                    chips[idx]++;
                    sum += weight;
                }
            }
        }
    }

    private static String oneRandomSet(int targetSum, int targetPairs) {
        int[] chips = new int[counts.length];
        int[] placements = placeChips(chips, targetPairs);
        adjustFactors(chips, placements, targetSum);
        int sum = sum(chips);
        StringBuffer sb = new StringBuffer();
        for (int placement : placements) {
            sb.append(weights[placement]);
            sb.append(" * ");
            sb.append(chips[placement]);
            sb.append(" + ");
        }
        sb.setLength(sb.length() - 2);
        sb.append(" = ");
        sb.append(sum);
        sb.append("\n");
        return sb.toString();
    }

    public static void main(String[] ARGV) {
        int targetSum = 5000;
        int targetPairs = 32;
        int targetResults = 15000; // Produce this many solutions
        buildCounts(data);
        StringBuffer sb = new StringBuffer();
        long timer = System.nanoTime();
        for (int i = 0; i < targetResults; i++) {
            sb.append(oneRandomSet(targetSum, targetPairs));
        }
        double seconds = (System.nanoTime() - timer) / 1000000000d;
        double millisPerSol = 1000 * seconds / targetResults;
        System.out.println(sb.toString());
        System.out.println(String.format("%d solutions in %1.3f seconds @ %1.3f millis per sol", targetResults, seconds,
                millisPerSol));
    }

}

Ответ 5

вы можете проверить "" Динамическое программирование ", динамическое программирование в основном экономит огромное время, в отличие от обычной рекурсии; поскольку он позволяет избежать повторного вычисления значений, сохраняя их в виде 2D-массива, этот учебник может помочь вам

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

Ответ 6

Изменить: я сохраняю этот ответ (на данный момент, по крайней мере), чтобы сохранить поток комментариев

Хорошо, я в замешательстве, но я все равно отправлю свои мысли и позже отредактирую/удалю, если я ошибаюсь. Если я действительно далек от знака, вы можете просто так сказать, и я удалю весь этот ответ.

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

Далее, мне кажется, что для каждого элемента в списке вы пытаетесь выполнить 100 (на самом деле 101) разных значений: x * 100, x * 99,..., x * 0. Если я прав, то следует, что размер проблемного пространства равен 100 ^ n, где n - количество элементов данных. Нет никакого способа изучить, что для n = 100, не говоря уже о n = 10000. Единственный способ, которым ваша программа может быть прекращена, заключается в том, что вы находите суммы в конце списка и завершаете те потоки расследования. (О, верно, теперь вы говорите мне, что прекращаете потоки, когда количество элементов с ненулевыми коэффициентами превышает 3, не 50, не 60, не имеет какого-либо переменного числа. Проблемное пространство все еще слишком велико.)

Фактически, по моему счету, ваши тестовые данные имеют 283 нулей. Таким образом, вы можете добавить 100 ^ 283 комбинаций этих элементов данных раз [1,100] к любому другому ответу, который вы получите. Учитывая, что количество частиц во Вселенной оценивается как 10 ^ 80, комбинация 100 ^ 283 невозможна для печати на бумаге.

Или иначе у меня что-то не так. Если да, пожалуйста, подскажите мне.

Ответ 7

Ваш код не соответствует вашему запросу, и поэтому неясно, как действовать.

Вы говорите, что список данных содержит отрицательные значения и содержит дубликаты. Вы приводите пример, который делает оба. Фактически, значения ограничены ненулевыми целыми числами в диапазоне [-200,200], но список данных составляет не менее 2000 и обычно 10 000 или более, поэтому должны быть дубликаты.

Давайте рассмотрим вашу "основную логику":

for (int c = 100; c >= 0; c--) {
    if (c * x_k == current.sum) { //if result is correct then save
        solutions.add(new Context(0, 0, newcoeff));
        continue;
     } else if (current.k > 0) { // recurse with next data element
         contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff));
     }
}

В другом месте вы указываете, что данные должны сортироваться в цифровом порядке, и вы начинаете с хвоста списка, k = n-1 (из-за нулевой индексации), поэтому сначала вы начинаете с самых больших. Предложение then завершает рекурсию. Хотя это может быть хорошо в проблеме, которую вы решаете, это не проблема, которую вы описываете, поскольку она игнорирует все комбинации меньших значений данных, которые суммируются до нуля.

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

Посмотрите, например, на последний элемент в вашем списке примеров 156 с целевой суммой 5000.

156 * 100 = 15600, поэтому он не будет соответствовать целевой сумме, пока вы не попадете в отрицательные числа. Конечно,

(100 * -100) + (100 * -6) + (100 * 156) = 5000

и эта комбинация работает. (Ваш набор данных не содержит -100, но он имеет два -40 и -20, поэтому, если вы хотите быть верными набору данных, вместо этого объедините их. Я использую -100, чтобы упростить пример и потому, что вы говорите, что набор данных может содержать -100.)

Но, конечно,

(100 * -100) + (100 * -6) + (c * -1) + (c * 1) + (100 * 156) = 5000

для любого c, поэтому на выходе вы получите 100 комбинаций (1 <= c <= 100). Но у вас есть 50 в наборе данных. Когда вы доберетесь до 100 * 50 = 5000, вы прекратите рекурсию, так что вы никогда не получите

(c * -1) + (c * 1) + (100 * 50) = 5000

Таким образом, либо ваш код, либо ваш оператор проблемы являются ошибками. Вероятно, и то, и другое, потому что даже без учета коэффициентов, 10 000 предметов, взятых по 60 за один раз, дают порядка 10 ^ 158 комбинаций, но помимо этого преждевременного прекращения рекурсии я не вижу ничего, что помешало бы вам проверить значение сумма всех этих комбинаций, и даже если при вычислении значений была нулевая стоимость, вы не могли бы сделать так много сравнений.

Ответ 8

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

См. http://en.m.wikipedia.org/wiki/Knapsack_problem#Approximation_algorithms

Ответ 9

Возможно, я ошибаюсь, но можно ли это рассматривать как целочисленный раздел (был номер треугольника, но я помнил, что я забыл)?

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

Я мог бы это сделать, но мне нужен большой набор данных. Интересно, хотя...

Обратитесь к гуру Knuth http://cs.utsa.edu/~wagner/knuth/fasc3b.pdf