Подбор суммы из набора чисел - помогите оптимизировать алгоритм

Имеется:
Массив из 96 элементов
Каждый элемент - число от 1 до 1.000.000 определенное рандомом
Сумма всех елементов массива приблизительно 13000000

Необходимо:
Сделать выборку из любого количества элементов, сумма которых равна заданой
Заданая сумма приблизительно равна 2500000

Методом тупого перебора придется перебрать 2^96 комбинаций
На 3ГГц процессоре, при условии что за один такт будет определяться одна комбинация для перебора всех комбинаций потребуется приблизительно 9*10^24 дней - за такой промежуток времени Земля перестанет существовать...

Найденые решения:

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

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

Вобщем, буду рад любым идеям.

Сообщение отредактировано: white_ng - 25.09.07, 17:10

white_ng
Тебе понадобится массив A длиной, равной необходимой сумме. i-й элемент массива означает, что мы можем набрать сумму, равную i.
Сначала A[0]=1, а все остальные равны нулю. Потом в цикле мы берем очередное число и для всех ненулевых элементов помечаем новые. Примерно это выглядит так:

for i := 1 to 96 do
  for j := sum-C[i] downto 0 do
    if A[j]<>0 then A[j+C[i]]=1;

И в конце, если A[sum]<>0, то данную сумму можно набрать. Чтобы узнать, как именно она набирается, нужно для каждого ненулевого A[i] запоминать, какой элемент массива C был использован.

ЗЫ. Это все называется метод динамического программирования. Сложность данного алгоритма O(sum*sizeof( C )). В твоем случае это примерно 2500000*96=240 млн. операций => меньше секунды работы компьютера.

Сообщение отредактировано: Pacific - 25.09.07, 19:50

Цитата Pacific @ 25.09.07, 19:47

white_ng
Тебе понадобится массив A длиной, равной необходимой сумме. i-й элемент массива означает, что мы можем набрать сумму, равную i.
Сначала A[0]=1, а все остальные равны нулю. Потом в цикле мы берем очередное число и для всех ненулевых элементов помечаем новые. Примерно это выглядит так:

for i := 1 to 96 do
  for j := sum-C[i] downto 0 do
    if A[j]<>0 then A[j+C[i]]=1;

И в конце, если A[sum]<>0, то данную сумму можно набрать. Чтобы узнать, как именно она набирается, нужно для каждого ненулевого A[i] запоминать, какой элемент массива C был использован.

ЗЫ. Это все называется метод динамического программирования. Сложность данного алгоритма O(sum*sizeof( C )). В твоем случае это примерно 2500000*96=240 млн. операций => меньше секунды работы компьютера.

А с чего вы взяли что числа целые?

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

Цитата Pacific @ 25.09.07, 20:17

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

Если ваше решение и правильное оно все равно имеет экспоненциальную сложность по времени и по памяти.

Но конечно лучше чем перебор

esperanto
Я написал, какую сложность имеет этот алгоритм. Фактически (при грамотной реализации) она равна количеству различных сумм, которые можно получить, помноженному на размер массива C. И в случае нецелых чисел становится равна C*2^C. Но если у него целые числа, то алгоритм достаточно эффективен. Вообще, это стандартная техника динамического программирования. А задача эта широко известна и называется "задача о сдаче с доллара".

Сообщение отредактировано: Pacific - 26.09.07, 04:55

А также как "задача о ранце (рюкзаке)".

Сообщение отредактировано: Pacific - 26.09.07, 06:00

2 Pacific

Спасибо, супер! Будем юзать.

Сложность для РС конечно повыше, но всеравно премлемая.

Необходимо только обойти нюансы.

1.

Допустим, на первой итерации когда массив А почти пустой берем первое число. допустим это 100. добавляется 0+100=100, А[100]=1

на второй итерации нужно добавить 110.
A[0]=1, 0+110=110, ок добавляем A[110]=1
дальше A[1]...A[99]=0, ниче не добавляем
A[100]=1, 100+110=210, добавляем A[210]=1

Но теперь, следующее ненулевое число - только что добавленое A[110]=1. Не будешь ведь добавлять еще и 110+110=220, A[220]=1, правильно?
Ведь каждый элемент может использоваться 1 раз.

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

2.

Теоретически возможно для каждой из сумм несколько вариантов составления, например 0+250=250, и 120+130=250
Кроме того, в исходном массиве могут быть одинаковые числа.

Думаю, вместо одномерного массива А можно создать двухмерный массив суммаХ96 куда в каждую строчку для каждой итерации будут записываться номера строчек из которых можно попасть в него на даной итерации, а если нельзя - то -1

***********************************************************************************************************

2 esperanto

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

Цитата white_ng

не будешь ведь добавлять еще и 110+110=220, A[220]=1, правильно?

Естественно, для этого как раз внутренний цикл в алгоритме проходится в обратном направлении. В результате, в 1 выставляются уже пройденные элементы, и ничего лишнего не добавляется. Массив сумма*96 не нужен, достаточно обойтись одномерным массивом. Только выставлять не единицу, а число от 1 до 96, обозначающее, что именно было использовано.

Добавлено 26.09.07, 08:31
Только этот алгоритм позволяет найти какой-то один способ набрать нужную сумму. Если тебе нужно найти все способы, придется делать двумерный массив, который ты описал, и потом его рекурсивно обходить, начиная с элемента A[sum,96].

2 Pacific

ок.
Завтра постну окончательное готовое решение когда сделаю.

2 All

Задачу можно считать решенной

Всем спасибо.

Цитата Pacific @ 26.09.07, 04:54

Но если у него целые числа, то алгоритм достаточно эффективен.

В теории эффективныи называют полиномиальные алгоритмы, а ваш экспоненциальный.

Сложность алгоритма определяется как функция длины входных данных.

-Added 26.09.07, 09:14

Цитата Pacific @ 25.09.07, 20:17

esperanto
Если они не целые, то задача NP-полная

Если они целые задача то же класса НП.

esperanto
Это все я понимаю. Но на практике (с программерской точки зрения) эффективными считаются те алгоритмы, которые укладываются в заданные ограничения по времени и по памяти при заданном диапазоне входных параметров. Так что даже экспоненциальные алгоритмы могут быть применимы на практике при небольшом размере входных данных. Автора топика этот алгоритм устроил, значит его можно считать эффективным.

Объясните, пожалуйста, как элементы массива А могут заполняться значениями, если стоит проверка

    if A[j]<>0 then A[j+C[i]]=1;

Изначально все элементы равны 0, кроме нулевого, индекс j до нулевого не доходит, следовательно A[j] всегда будет не равно 0. Как же тогда выполнить A[j+C[i]]=1 ?

asd
Ещё раз код из поста №2 (внимательно смотри вторую строчку):

for i := 1 to 96 do
  for j := sum-C[i] downto 0 do
    if A[j]<>0 then A[j+C[i]]=1;

Понятно...
вот у меня такой простой код для проверки:

        int n = 4;
        int k = 8;
        int[] arC = {6,5,3,2};
        int[] arA = new int[k+1];
        arA[0] = 1;
        for (int i = 1; i < n; i++){
            for (int j = k - arC[i]; j >= 0; j--){
                if (arA[j] != 0)
                    arA[j + arC[i]]= 1;
            }
            
        }
        for (int i = 0; i < k; i++ ){
            System.out.println(arA[i]);
        }

Выдает 1 0 1 1 0 1 0 1
Если индекс в этой последовательности равен возможности получить суммы равную индексу, то ответ получается 0, 2,3,5,7... А 8? 8-это искомая сумма...

Сообщение отредактировано: asd - 15.02.08, 11:33