Задача идеальной суммы с фиксированным размером подмножества

Question

Я ищу алгоритм с наименьшей сложностью во времени, который решал бы вариант задачи идеальной суммы (изначально: поиск всех комбинаций подмножеств переменного размера из массива [*] целых чисел размера n, сумма которого до указанного c число x), где размер комбинации подмножества имеет фиксированный размер k и возвращает возможные комбинации без прямых, а также косвенных (когда есть комбинация, содержащая точно такие же элементы из другого в другом порядке) дублируется.

Я знаю, что эта проблема является NP-сложной, поэтому я не ожидаю идеального общего решения, но что-то, что могло бы, по крайней мере, работать в разумное время в моем случае, с n близко к 1000 и k около 10

Вещи, которые я пробовал до сих пор:

• Поиск комбинации, а затем выполнение последовательных модификаций ее и ее модификаций

  Предположим, я есть массив, например:

s = [1,2,3,3,4,5,6,9]

Итак, у меня есть n = 8, и я бы хотел x = 10 для k = 3

Я нашел благодаря некоему непонятному методу (грубой силе?) Подмножество [3,3,4]

Из этого подмножества я нахожу другие возможные комбинации, вынимая из него два элемента и заменяя их другими элементами, сумма которых одинакова, т.е. (3, 3) можно заменить на (1, 5), поскольку оба имеют одинаковую сумму, а заменяющие числа еще не используются. Итак, я получаю другое подмножество [1,5,4], затем повторяю процесс для всех полученных подмножеств ... бесконечно?

Основная проблема, предлагаемая здесь, заключается в том, что трудно определить, когда это будет сделано, и этот метод скорее чаоти c. Я придумал несколько вариантов этого метода, но они действительно находятся в стадии разработки.

• Перебор набора для перечисления всех k длинных комбинаций, которые в сумме составляют x

Довольно понятно. Это наивный метод, который в моем случае не работает, так как у меня есть довольно большие n и k, которые недостаточно малы, чтобы избежать катастрофически большого количества комбинаций (величина количества комбинаций равна 10. ^ 27!)

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

Что бы вы посоветовали? (Фрагменты могут быть на любом языке, но я предпочитаю C ++)

[*] Чтобы снять сомнения относительно того, может ли базовая коллекция содержать дубликаты, я использовал термин «массив» вместо «установить» в точнее. Коллекция может содержать повторяющиеся целые числа в моем случае и довольно много, с 70 разными целыми числами для 1000 элементов (количество округлено), например

Answer 1

Вот полное решение в Python. Перевод на C ++ предоставляется читателю.

Как и обычная сумма подмножества, генерация двусвязной сводки решений является псевдополиномиальной. Это O(count_values * distinct_sums * depths_of_sums). Однако на самом деле их повторение может быть экспоненциальным. Но использование генераторов таким способом позволяет избежать использования большого количества памяти для создания этого списка, даже если для его выполнения может потребоваться много времени.

from collections import namedtuple
# This is a doubly linked list.
# (value, tail) will be one group of solutions.  (next_answer) is another.
SumPath = namedtuple('SumPath', 'value tail next_answer')

def fixed_sum_paths (array, target, count):
    # First find counts of values to handle duplications.
    value_repeats = {}
    for value in array:
        if value in value_repeats:
            value_repeats[value] += 1
        else:
            value_repeats[value] = 1

    # paths[depth][x] will be all subsets of size depth that sum to x.
    paths = [{} for i in range(count+1)]

    # First we add the empty set.
    paths[0][0] = SumPath(value=None, tail=None, next_answer=None)

    # Now we start adding values to it.
    for value, repeats in value_repeats.items():
        # Reversed depth avoids seeing paths we will find using this value.
        for depth in reversed(range(len(paths))):
            for result, path in paths[depth].items():
                for i in range(1, repeats+1):
                    if count < i + depth:
                        # Do not fill in too deep.
                        break
                    result += value
                    if result in paths[depth+i]:
                        path = SumPath(
                            value=value,
                            tail=path,
                            next_answer=paths[depth+i][result]
                            )
                    else:
                        path = SumPath(
                            value=value,
                            tail=path,
                            next_answer=None
                            )
                    paths[depth+i][result] = path

                    # Subtle bug fix, a path for value, value
                    # should not lead to value, other_value because
                    # we already inserted that first.
                    path = SumPath(
                        value=value,
                        tail=path.tail,
                        next_answer=None
                        )
    return paths[count][target]

def path_iter(paths):
    if paths.value is None:
        # We are the tail
        yield []
    else:
        while paths is not None:
            value = paths.value
            for answer in path_iter(paths.tail):
                answer.append(value)
                yield answer
            paths = paths.next_answer

def fixed_sums (array, target, count):
    paths = fixed_sum_paths(array, target, count)
    return path_iter(paths)

for path in fixed_sums([1,2,3,3,4,5,6,9], 10, 3):
    print(path)

Кстати, для вашего примера вот решения:

[1, 3, 6]
[1, 4, 5]
[2, 3, 5]
[3, 3, 4]

Answer 2

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

Сделайте трехмерный массив, список или вектор с внешней размерностью x-1 например: A[][][]. Каждый элемент A[p] этого списка содержит список возможных подмножеств с суммой p.

Мы можем пройти через все элементы (вызвать текущий элемент item) начального «набора» (я заметил повторяющиеся элементы в ваш пример, так что это не правда набор).

Теперь просканируем A[] список от последней записи до начала. (Этот трюк помогает избежать повторного использования одного и того же элемента).

Если A[i - item] содержит подмножества с размером <<code>k, мы можем добавить все эти подмножества к A[i], добавив item.

После полного сканирования A[x] будет содержать подмножества размером k и меньше, имея сумму x, и мы можем фильтровать только те, которые имеют размер k

Пример вывода моего быстрого -made Delphi программа для следующих данных:

Lst := [1,2,3,3,4,5,6,7];
k := 3;
sum := 10;

  3  3  4
  2  3  5  //distinct 3's
  2  3  5
  1  4  5
  1  3  6   
  1  3  6   //distinct 3's
  1  2  7

Чтобы исключить варианты с отдельными повторяющимися элементами (при необходимости), мы можем использовать непервое вхождение только для подмножеств, уже содержащих первое вхождение элемента ( так что 3 3 4 будет действительным, а второе 2 3 5 не будет сгенерировано)

Я буквально перевожу свой Delphi код на C ++ (странно, я думаю :)

int main()
{
    vector<vector<vector<int>>> A;
    vector<int> Lst = { 1, 2, 3, 3, 4, 5, 6, 7 };

    int k = 3;
    int sum = 10;
    A.push_back({ {0} });  //fictive array to make non-empty variant
    for (int i = 0; i < sum; i++)
        A.push_back({{}});


    for (int item : Lst) {
        for (int i = sum; i >= item; i--) {
            for (int j = 0; j < A[i - item].size(); j++) 
                if (A[i - item][j].size() < k + 1  && 
                    A[i - item][j].size() > 0) {
                    vector<int> t = A[i - item][j];
                    t.push_back(item);
                    A[i].push_back(t);  //add new variant including current item
                }
        }
    }
         //output needed variants
    for (int i = 0; i < A[sum].size(); i++)
        if (A[sum][i].size() == k + 1) {
            for (int j  = 1; j < A[sum][i].size(); j++) //excluding fictive 0
                cout << A[sum][i][j] << " ";
        cout << endl;
    }
}

Answer 3

Метод грубой силы с использованием рекурсии может выглядеть так ...

Например, для заданного набора переменных x, k может работать следующий псевдокод:

setSumStructure find(int[] set, int x, int k, int setIdx)
{
   int sz = set.length - setIdx;
   if (sz < x) return null;
   if (sz == x) check sum of set[setIdx] -> set[set.size] == k.  if it does, return the set together with the sum, else return null;
   
   for (int i = setIdx; i < set.size - (k - 1); i++)
      filter(find (set, x - set[i], k - 1, i + 1));

   return filteredSets;
}

Answer 4

Вы должны сначала отсортировать так называемый массив. Во-вторых, вы должны определить, действительно ли проблема разрешима, чтобы сэкономить время ... Итак, что вы делаете, вы берете последние k элементов и смотрите, больше ли их сумма или равна значению x, если оно меньше, вы сделали, невозможно сделать что-то подобное .... Если это на самом деле равно, да, вы тоже сделали, нет других перестановок .... O (n) чувствует себя хорошо, не так ли ?? Если он больше, то у вас много работы ... Вам нужно сохранить все перестановки в отдельном массиве .... Затем вы go вперед и заменяете наименьшее из k чисел на наименьший элемент в массиве .... Если это все еще больше, чем x, вы делаете это для второго и третьего и так далее, пока не получите что-то меньшее, чем x. Как только вы достигнете точки, в которой ваша сумма меньше x, вы можете go вперед и начать увеличивать значение последней позиции, на которой вы остановились, до тех пор, пока вы не нажмете x .... Как только вы нажмете x, это будет ваша комбинация. ... Затем вы можете go вперед и получить предыдущий элемент, поэтому, если у вас было 1,1,5, 6 в вашей штуке, вы можете go вперед и взять 1, а также добавить его к своему наименьшему элементу, 5, чтобы получить 6, затем вы проверите, можете ли вы записать это число 6 как комбинацию двух значений, вы остановитесь, как только нажмете значение ... Затем вы можете повторить и для других .... Проблема может быть решается за O (n!) раз в худшем случае .... Я бы не стал предлагать вам 10 ^ 27 комбинаций, то есть у вас более 10 ^ 27 элементов, ммммм плохая идея, у вас даже есть столько места ??? Это как 3 бита для заголовка и 8 бит для каждого целого числа, вам понадобится 9,8765 * 10 ^ 25 терабайт только для хранения этого замкнутого массива, больше памяти, чем суперкомпьютер, вам следует беспокоиться о том, сможет ли ваш компьютер даже хранить этого монстра, а не если вы может решить проблему, что многие комбинации, даже если вы найдете решение quadrati c, оно взломает sh ваш компьютер, и вы знаете, что quadrati c далек от O (n!) ...