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

[Qwe1]

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


int NUM[] = {10,20,30,40,50, <...>};
int COUNT = sizeof(NUM)/sizeof(int);
int SUM = 35;
int i,j,k,n;

<...>

for(i=0;i<COUNT;i++)
for(j=0;j<COUNT;j++)
for(k=0;k<COUNT;k++)
for(n=0;n<COUNT;n++)
{
if((i!=j && i!=k && i!=n) && (j!=k && j!=n) && (k!=n))
{
if(NUM[i] + NUM[j] + NUM[k] + NUM[n] == SUM)
printf("%d %d %d %d\n",i,j,k,n);
}
}

[ivank]

Qwe1
Элементы положительные? Ограничение сверху на сумму есть? Если есть ограничение на сумму и элементы положительные, то можно применить динамическое программирование. Вариант с перебором всех комбинаций работает только при небольшом размере массива.

[Gerdewski]

Каждый новый цикл нужно начинать с элемента, большего на 1 предыдущего.
т.е. не j=0 , а j=i+1 по-быстрее так заработает.
(наверное это имел ввиду ivank)
Складывать нужно обязательно 4 числа? А если сумма 3х, 2х или одно число равно заданному значению, как поступать тогда?

[Qwe1]

ivank
1) Элементы все положительные;
2) "Определенное начение" (с которым идет сравнение) всегда меньше суммы всех элементов (примерно в 3 раза).

Gerdewski
1) У меня изначально (в цикле for) было так i=0, j=1, k=2, n=3, но потом я решил, что для полноты перебора необходимо проинициализировать именно нулями. Так ли это (?)
2) Аналогичные циклы у меня реализованы для 2, 3, ..., 7 переменных. Для 7 переменных, если не ошибаюсь, число комбинаций = число элементов в степени 7. Для 42 элементов имеем 230 539 333 248 комбинаций. На моем компе вычислялось почти 30 минут.

Знал бы, как прикреплять сюда файлы, выложил бы весь исходник :(

[ivank]

Qwe1
Так чему равна максимальная сумма? Приблизительно?

Если перебирать все комбинации, то это будет "цэ из эн по ка" операций, т.е. n!/(k!*(n-k!), где n - размер массива, k - число элементов в комбинации. Это выражение растёт очень быстро, а посему не подходит ни в одном практическом случае. Это я к тому, что перебор - не выход.

[Qwe1]

ivank
"цэ из эн по ка" - это, вроде, число сочетаний - количество способов выбрать K из N различных предметов. Вычисляется по следующей формуле: CNK = ANK/K! = N*(N-1)*...*(N-K+1)/K! = N!/(K!*(N-K)!). Так что, я не прав по поводу числа комбинаций (см. здесь (http://forum.oszone.net/post-484685-4.html)).

Мне нужен хотя бы какой-нибудь способ. Я бы запустил алгоритм "в лоб" на каком-нибудь более-менее мощном компе и получил бы результат (здесь отрицательный результат - тоже результат). Поэтому хотелось бы этот алгоритм хоть как-нибудь соорудить. Если предложенный мною способ вычисления для 4 переменных верный, то я запулю еще для 8-ми переменных и поставлю на вычисление!! Хотя, если кто-то предложит более быстрый и т.д. код, буду рад :)

[ivank]

Qwe1
ВЫ упорно не отвечаете на мой вопрос. Какова максимальная сумма всех элементов? Каков максимальный размер массива? От этого зависит применимость того решения, которое есть у меня. Его асимптотическая сложность O(mn), где m - размер массива, n - максимальная сумма. Затраты памяти - O(n). Таким образом при отсутвии ограничения на максимальную сумму нам банально не хватит времени и памяти.

P.S. В предыдущем посте я наврал. На самом деле при "лобовом подходе" перебирать надо даже SUM(k=1, n, C_n_k). Т.е. сумма всех цэ из эн по ка для всех ка от 1 до эн. Это ещё хуже.

[Qwe1]

Вот реальный пример набора данных: 42 элемента, сумма = 1 233 188, значение для сравнения = 350 000. Сам массив:
int NUM[] = {
197900,70584,65006,39893,27638,
29448,17220,7750,39032,2870,
2010,22386,93275,20090,10906,
36162,4133,40180,64575,34440,
6027,8754,22960,4879,22960,
18311,39893,27638,58896,24108,
22386,2727,36162,4879,4133,
34440,5740,2727,15355,1665,
34440,8610};

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

[ivank]

Ну тогда всё просто. (Если среда нормальная 32-битная и не проблема выделить 5 метров памяти).

Примерно так.
int sum = 0;
int i, j;
for (i = 0; i < size; ++i)
sum += NUM[i];

int *way = new int[sum+1];
for (i = 0; i < size; ++i)
way = 0;

way[0] = 1;

for (i = 0; i < size; ++i)
for (j = sum; j > 0; --j)
if (j >= NUM[i] && way[j-NUM[i]] != 0)
way[j] = NUM[i];

// n - требуемая сумма
if (!way[n])
printf("Всё плохо\n");
else
{
printf("Всё хорошо, путь:\n");
for (i = n; i != 0; i -= way[i])
printf("%d\n", way[i]);
}

delete[] way;

Не проверял, так как сейчас времени нет. Вечером может проверю. Но идея ясна, я надеюсь.

[Qwe1]

ivank
Честно, мне не очень понятно :blush:
Всего 42 элемента. Надо найти такие, чья сумма равнялась 350 000. Теоритически их может быть и 2. Для предложенного набора - не 2 и не 3 точно. Может 6 или 7. А скорее всего - их вообще нет. Это и надо проверить!

Поэтому, если n - требуемая сумма (т.е. 350 000), то way[350000] ??

[ivank]

Qwe1
Ладно. Рассмотрим всё по порядку. Пусть у нас есть m целых положительных элементов a[i] и трубеится найти можно ли из них составить сумму равную n. Создадим массив can[i][k] размера m на n+1. can[i][k] = 1, если мы можем получить каким-то образом суммируя только элементы a[0]...a[i] сумму равную k. Нас интерисует значение can[m][n], т.е. можем ли мы получить используя элементы a[0]...a[m] сумму n.

Очевидно can[0][k] = 0, для всех k != a[0] и k != 0. can[0][0] = 1 и can[0][a[0]] = 1. Т.е. используя один элемент мы можем получить только сумму равную 0 или этому элементу.

Рассмотрим как по массиву can[i-1] можно построить can[i]. Очевидно, что используя i элементов всегда можно получить те же суммы, что и используя i=1 элемент (просто не добавляя к прежним суммам i-й элемент). Т.е. если can[i-1][k]=1, то can[i][k]=1 так же. Кроме того, к любой из прежних сумм мы можем добавить i-й элемент, т.е. если can[i-1][k]=1, то can[i][k+a[i]]=1 так же. Во всех остальных случаях can[i][k]=0.

Реализация вышеописанного в (псевдо)коде будет выглядеть вот так:
int can[m][max_sum+1], i, j;
for (i = 0; i < m; ++i)
for (j = 0; j <= max_sum; ++j)
can[i][j] = 0;
can[0][0] = can[0][a[0]] = 1;
for (i = 1; i < m; ++i)
{
for (j = 0; j < max_sum; ++j)
can[i][j] = can[i-1][j];
for (j = 0; j < max_sum; ++j)
if (can[i-1][j])
can[i][j+a[j]] = 1;
}

Пользуясь тем фактом, что у нас в can[i] по сравнению с can[i-1] только дописываются единички, а так же тем, что все элементы мы можем модифицировать массив прям на месте, вместо того, что бы иметь цепочку массивов can[0]...can[m].

Вот так:int can[max_sum], i, j;
for (i = 0; i <= max_sum; ++i)
can[i] = 0;
can[0] = 1;
for (i = 0; i < m; ++i)
for (j = max_sum; j > 0; --j)
if (j >= a[i] && can[j-a[i]])
can[j] = 1;

В результате can[n] = 1, если можно получить сумму равную n.

Теперь, если вместо 1 в can[k] ставить то, число которое мы добавили для получения суммы k, то можно будет получить список всех чисел, которые необходимо было просуммировать.
b1 = can[k] - первое число
b2 = can[k-b1] - второе число
b3 = can[k-b1-b2] - третье число
b4 = can[k-b1-b2-b3] - четвёртое число.
итд

В коде это будет так:
printf("Всё хорошо, путь:\n");
for (i = n; i != 0; i -= way[i])
printf("%d\n", way[i]);

[Vlad Drakula]

ivank
чего то ваш алгоритм есть слишком много памяти...
мне вот кажется что придумать алгоритм который есть в max_sum+1 раз меньше памяти не так и сложно...
чтобы не быть голословным скоро приведу пример...

[Vlad Drakula]

код на C# котонрый выводит все элементы...


using System;

namespace summ
{
class Class1
{
static void su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
{
for(;i < l; i++)
{
if(corsize + m[i] == size)
{
for(int j = 0; j <= p; j ++)
{
Console.Write("{0} + ", m[s[j]]);
}

Console.WriteLine("{0} = {1};", m[i], size);
}
else if(corsize + m[i] < size)
{
s[p + 1] = i;
su(m, s, i + 1, p + 1, l, size, corsize + m[i]);
}
}
}

static void summ(int[] m, int l, int size)
{
int[] s = new int[l];
su(m, s, 0, -1, l, size, 0);
}

static void Main(string[] args)
{
int l = 1000;
int[] m = new int[l];

for(int j = 0; j < l; j ++)
{
m[j] = j;
}

summ(m,l, 10);
}
}
}

[ivank]

Vlad Drakula
Ты просто рекурсивно перебираешь все возможные суммы. Выше уже давалась оценка их количества. Если коротко: афигеть как много. Твой код будет мягко говоря очень долго думать в любом сколь-нибудь сложном случае (время его работы в худшем случае - 2^n, где n - число чисел). Мой гарантированно закончится за O(m*n), где n - число чисел, m - требуемая сумма (максимальная нас не интересует, тут я немножко слажал в описании выше.) Памяти потребуется m. Да, это много. Но это разумная плата за полиномиальное время работы алгоритма вместо экспоненциального.

Сейчас mono соберу и приведу тест, на котором твой код сильно задумается.

[ivank]

Скачал моно. Прогнал простейший тест.

Итак, сначала моя программа в первый раз доведённая до работающего состояния (читай: в первый раз скормил компилятору и поправил очевидные очепятки).
#include <stdio.h>

int main()
{
/*
// тест, приведённый оригинальным автором поста
int num[] = {
197900,70584,65006,39893,27638,
29448,17220,7750,39032,2870,
2010,22386,93275,20090,10906,
36162,4133,40180,64575,34440,
6027,8754,22960,4879,22960,
18311,39893,27638,58896,24108,
22386,2727,36162,4879,4133,
34440,5740,2727,15355,1665,
34440,8610
};
const int n = sizeof(num)/sizeof(int);
const int m = 350000;
*/
// мой тест, вешает программу Влада
const int n = 1000; // количество чисел в наборе
int num[n]; // сами числа. Втупую подряд
for (int i = 0; i < n; ++i)
num[i] = 1+i;
const int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого

int *way = new int[m+1];
for (int i = 0; i <= m; ++i)
way[i] = 0;

way[0] = 1;

for (int i = 0; i < n; ++i)
for (int j = m; j > 0; --j)
if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
way[j] = num[i];

if (!way[m])
printf("Всё плохо\n");
else
{
printf("Всё хорошо, путь:\n");
for (int i = m; i != 0; i -= way[i])
printf("%d\n", way[i]);
}

delete[] way;
return 0;
}
Отрабатывает за секунду в случае "сложного" теста. Мгновенно на примере приведённом автором вопроса.

Программа влада с тем же синтетическим тестом. Не заканчивается никогда.using System;

namespace summ
{
class Class1
{
static void su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
{
for(;i < l; i++)
{
if(corsize + m[i] == size)
{
for(int j = 0; j <= p; j ++)
{
Console.Write("{0} + ", m[s[j]]);
}

Console.WriteLine("{0} = {1};", m[i], size);
}
else if(corsize + m[i] < size)
{
s[p + 1] = i;
su(m, s, i + 1, p + 1, l, size, corsize + m[i]);
}
}
}

static void summ(int[] m, int l, int size)
{
int[] s = new int[l];
su(m, s, 0, -1, l, size, 0);
}

static void Main(string[] args)
{
int l = 1000;
int[] m = new int[l];

for(int j = 0; j < l; j ++)
{
m[j] = j+1;
}

summ(m,l, l*(l+1)/2-1);
}
}
}

[Vlad Drakula]

ivank
Выше уже давалась оценка их количества.
1) тыкни носом в отценку.
2) дненм проведу этот тест и посмотнрю на результат.

[ivank]

P.S. В предыдущем посте я наврал. На самом деле при "лобовом подходе" перебирать надо даже SUM(k=1, n, C_n_k). Т.е. сумма всех цэ из эн по ка для всех ка от 1 до эн. Это ещё хуже.
Честно говоря, я склоняюсь к мысли, что эта сумма будет равна 2^n. Поскольку бинарных наборов длины n может быть всего 2^n. А каждый бинарный набор характеризует собой какую-то уникальную сумму (комбинацию чисел). Перебрать их, если делать втупую, надо все. В общем, чистая экспонента.

P.S. Только что проверил эту мысль на бумажке. Действительно, SUM(k=1, n, C_n_k) = 2^n.

[Vlad Drakula]

ivank



using System;

namespace summ
{
class Class1
{
static bool su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
{
for(;i < l; i++)
{
if(corsize + m[i] == size)
{
for(int j = 0; j <= p; j ++)
{
Console.Write("{0} + ", m[s[j]]);
}

Console.WriteLine("{0} = {1};", m[i], size);

return true;
}
else if(corsize + m[i] < size)
{
s[p + 1] = i;
if(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
{
return true;
}
}
}

return false;
}

static void summ(int[] m, int l, int size)
{
int[] s = new int[l];
su(m, s, 0, -1, l, size, 0);
}

static void summ2(int[] num, int n, int size)
{
int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого

int[] way = new int[m+1];
for (int i = 0; i <= m; ++i)
way[i] = 0;

way[0] = 1;

for (int i = 0; i < n; ++i)
for (int j = m; j > 0; --j)
if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
way[j] = num[i];

if (way[m] == 0)
Console.WriteLine("Всё плохо");
else
{
Console.Write("Всё хорошо, путь: ");
for (int i = m; i != 0; i -= way[i])
Console.Write("{0} ", way[i]);
Console.WriteLine("");
}
}

static void Main(string[] args)
{
DateTime d1, d2;
int l = 500;
int[] m = new int[l];

for(int j = 0; j < l; j ++)
{
m[j] = l - j;
}

d1 = DateTime.Now;
summ(m,l, l*(l+1)/2-1);
d2 = DateTime.Now;
Console.WriteLine("eval time: {0}", d2 - d1);

d1 = DateTime.Now;
summ2(m,l, l*(l+1)/2-1);
d2 = DateTime.Now;
Console.WriteLine("eval time: {0}", d2 - d1);
}
}
}



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

int l = 500;
eval time: 00:00:00.0200288
eval time: 00:00:00.5708208
int l = 700;
eval time: 00:00:00.0300432
eval time: 00:00:03.7754288

разница в времени работы не в вашу пользу...

[ivank]

Vlad Drakula
Влад. Давай не будем подгонять входные данные. Вернее, моей программе всё равно, подгоняй их или нет. Время работы зависит только от требуемой суммы и числа элементов. Для твоей программы имеет значение то, в какой последовательности заданы элементы и какую сумму мы ищем. При определённых входных данных она подвисает, что я продемонстрировал. Понятно, что в том случае, когда первый же перебор заканчивается успешно твоя программа отработает мгновенно. Но это _подгон_.

Давай посмотрим как ты изменил мой тест: for(int j = 0; j < l; j ++)
{
m[j] = l - j;
}

d1 = DateTime.Now;
summ(m,l, l*(l+1)/2-1);
d2 = DateTime.Now;
Console.WriteLine("eval time: {0}", d2 - d1);

Теперь l*(l+1)/2-1 - это не сумма всех чисел кроме первого. Это сумма всех чисел, кроме последнего. При твоём порядке перебора это будет вторая возможность рассмотренная твоей программой.

Приведу генератор теста, на котором твоя программа будет виснуть всегда. Мы просто ищем сумму всех элементов, кроме элементов равных минимальному. Причём один из минимальных элементов мы кладём в середину массива. Можешь заполнять исходный массив как хочешь - программа будет думать долго всегда. Тест синтетический, но он показывает, что твой алгоритм в худшем случае не работает, и что время моего не зависит от входных данных (вернее, зависит только от m и n, но не самих суммируемых чисел).

Можешь попробовать заполнять m как хочешь. Увидишь, что твой код по прежнему очень долго думает.

Вот код. Я немного его модифицировал. В частности убрал вывод на консоль, чтобы не мешал на время смотреть. А так же сделал "свою" функцию зависимой от третьего параметра. Кроме того, поменял местами вызовы своей функции и твоей. Т.к. твоя подвисает -> до выполнения моей никогда дело не дохдит, если твоя первая.

using System;

namespace summ
{
class Class1
{
static bool su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
{
for(;i < l; i++)
{
if(corsize + m[i] == size)
{
/*
for(int j = 0; j <= p; j ++)
{
Console.Write("{0} + ", m[s[j]]);
}

Console.WriteLine("{0} = {1};", m[i], size);
*/
return true;
}
else if(corsize + m[i] < size)
{
s[p + 1] = i;
if(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
{
return true;
}
}
}

return false;
}

static void summ(int[] m, int l, int size)
{
int[] s = new int[l];
su(m, s, 0, -1, l, size, 0);
}

static void summ2(int[] num, int n, int m)
{
int[] way = new int[m+1];
for (int i = 0; i <= m; ++i)
way[i] = 0;

way[0] = 1;

for (int i = 0; i < n; ++i)
for (int j = m; j > 0; --j)
if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
way[j] = num[i];
/*
if (way[m] == 0)
Console.WriteLine("Всё плохо");
else
{
Console.Write("Всё хорошо, путь: ");
for (int i = m; i != 0; i -= way[i])
Console.Write("{0} ", way[i]);
Console.WriteLine("");
}
*/
}

static void Main(string[] args)
{
DateTime d1, d2;
int l = 500;
int[] m = new int[l];

for(int j = 0; j < l; j ++)
{
m[j] = l - j;
}

// Старый тест
d1 = DateTime.Now;
summ2(m, l, l*(l+1)/2-1);
d2 = DateTime.Now;
Console.WriteLine("ivank's eval time: {0}", d2 - d1);

d1 = DateTime.Now;
summ(m, l, l*(l+1)/2-1);
d2 = DateTime.Now;
Console.WriteLine("vlad's eval time: {0}", d2 - d1);

// Новый тест
// Требуется сумма всех элементов, кроме элемента из середины массива
// Поиск минимального элемента и перестановка его в середину массива
int min = 0;
for (int j = 0; j < l; ++j)
if (m[j] < m[min])
min = j;
int temp = m[min];
m[min] = m[l/2];
m[l/2] = temp;

// Нужна сумма всех элементов за исключением равных минимальному
int needed = 0;
for (int j = 0; j < l; ++j)
if (m[j] != m[l/2])
needed += m[j];

d1 = DateTime.Now;
summ2(m, l, needed);
d2 = DateTime.Now;
Console.WriteLine("ivank's eval time: {0}", d2 - d1);

d1 = DateTime.Now;
summ(m, l, needed);
d2 = DateTime.Now;
Console.WriteLine("vlad's eval time: {0}", d2 - d1);

}
}
}

(ушёл, буду в восемь)

[Vlad Drakula]

ivank



using System;

namespace summ
{
class Class1
{
static bool su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
{
for(;i < l; i++)
{
if(corsize + m[i] == size)
{
for(int j = 0; j <= p; j ++)
{
Console.Write("{0} + ", m[s[j]]);
}

Console.WriteLine("{0} = {1};", m[i], size);

return true;
}
else if(corsize + m[i] < size)
{
s[p + 1] = i;
if(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
{
return true;
}
}
}

return false;
}

static void QSort(int[] ar, int size)
{
int left, right, ixLeft, ixRight;
int[] borderLeft = new int[100];
int[] borderRight = new int[100];
int stach = 0;
int copy;
int x;
Random r = new Random();
borderLeft[0] = 0;
borderRight[0] = size - 1;
while(stach >= 0)
{
ixLeft = left = borderLeft[stach];
ixRight = right = borderRight[stach];
stach--;

while(left < right)
{
x = ar[r.Next(left, right)];
ixLeft = left;
ixRight = right;

while(ixLeft <= ixRight)
{

while(ar[ixLeft] > x)
{
ixLeft++;
}
while(ar[ixRight] < x)
{
ixRight--;
}

if(ixLeft <= ixRight)
{
copy = ar[ixLeft];
ar[ixLeft] = ar[ixRight];
ar[ixRight] = copy;
ixLeft++;
ixRight--;
}
}

if(ixRight - left < right - ixLeft)
{
stach++;
borderLeft[stach] = ixLeft;
borderRight[stach] = right;
right = ixRight;
}
else
{
stach++;
borderLeft[stach] = left;
borderRight[stach] = ixRight;
left = ixLeft;
}
}
}
}

static void summ(int[] m, int l, int size)
{
QSort(m, l);
int[] s = new int[l];
su(m, s, 0, -1, l, size, 0);
}

static void summ2(int[] num, int n, int size)
{
int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого

int[] way = new int[m+1];
for (int i = 0; i <= m; ++i)
way[i] = 0;

way[0] = 1;

for (int i = 0; i < n; ++i)
for (int j = m; j > 0; --j)
if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
way[j] = num[i];

if (way[m] == 0)
Console.WriteLine("Всё плохо");
else
{
Console.Write("Всё хорошо, путь: ");
for (int i = m; i != 0; i -= way[i])
Console.Write("{0} ", way[i]);
Console.WriteLine("");
}
}

static void Main(string[] args)
{
DateTime d1, d2;
int l = 800;
int[] m = new int[l];

for(int j = 0; j < l; j ++)
{
m[j] = l - j;
}

// Новый тест
// Требуется сумма всех элементов, кроме элемента из середины массива
// Поиск минимального элемента и перестановка его в середину массива
int min = 0;
for (int j = 0; j < l; ++j)
if (m[j] < m[min])
min = j;
int temp = m[min];
m[min] = m[l/2];
m[l/2] = temp;

// Нужна сумма всех элементов за исключением равных минимальному
int needed = 0;
for (int j = 0; j < l; ++j)
if (m[j] != m[l/2])
needed += m[j];


d1 = DateTime.Now;
summ2(m,l, needed);
d2 = DateTime.Now;
Console.WriteLine("ivank's time: {0}", d2 - d1);

d1 = DateTime.Now;
summ(m,l, needed);
d2 = DateTime.Now;
Console.WriteLine("vlad's time: {0}", d2 - d1);
}
}
}



ivank's time: 00:00:03.7854432
vlad's time: 00:00:00.0300432

еще раз придумаешь новый тест?