[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)!). Так что, я не прав по поводу числа комбинаций (см. здесь).

Мне нужен хотя бы какой-нибудь способ. Я бы запустил алгоритм "в лоб" на каком-нибудь более-менее мощном компе и получил бы результат (здесь отрицательный результат - тоже результат). Поэтому хотелось бы этот алгоритм хоть как-нибудь соорудить. Если предложенный мною способ вычисления для 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
Честно, мне не очень понятно
Всего 42 элемента. Надо найти такие, чья сумма равнялась 350 000. Теоритически их может быть и 2. Для предложенного набора - не 2 и не 3 точно. Может 6 или 7. А скорее всего - их вообще нет. Это и надо проверить!

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