Рекурсивный алгоритм, определяющий группу чисел из массива, чтобы сумма=m

что бы сумма=m



Исчу бессрочно книги и лекции по математике (матстатистика, оптимизация...)

 

Это NP-полная задача. Даже в таком частном случае:
m = сумма всех чисел массива / 2

См. Problems 41 и 42 в Annotated List of Selected NP-complete Problems.

Цитата


maxal писал(а) :
Это NP-полная задача. Даже в таком частном случае:
m = сумма всех чисел массива / 2

См. Problems 41 и 42 в Annotated List of Selected NP-complete Problems.

Спасибо maxal!

Да, вы правы, "Problems 42"-индентична условиям вышеуказанной задачи.
Не могли бы вы мне объяснить:
1)что такое NP-полная задача?
2)что имеется в виду под выражением:"Даже в таком частном случае:
m = сумма всех чисел массива / 2"?
3)или в вышеуказанной ссылке "Annotated List of Selected NP-complete Problems" имеются также указания к решению "Problems 42"?

Ещё раз хочу поблагодарить вас maxal за отклик, тем не менее

хочу привести свой алгоритм решения задачи который основан на принципе:

"для того что бы доказать что существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[1,...,i,...,n], так что-бы сумма всех чисел вышеуказанной группы=m - достаточно доказать, что существует элемент массива A[ i ],
такой что существует группа чисел, являющихся подмножеством к
A[ i+1,...,n ], сумма которых равна m - А[ i ]".



Условие задачи:
a) пусть будет дан массив разных целых чисел A[1,...,i,...,n],
b)дано целое число m.

precondition: алгоритм получает исходное число i=1, массив разных целых чисел A[i,...,n],целое число m.
postcondition: алгоритм выдаёт результат TRUE или FALSE.

Алгоритм:

1)найди или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву A[i+1,...,n], так что-бы сумма всех чисел вышеуказанной группы=m-A[ i ].


2)если условие1 TRUE, рекурсия останавливается и алгоритм выдаёт результат TRUE
в противном случае(т.е. если условие1 FALSE) :
если условие i < n TRUE - инкрементируй i на 1, (т.е. i = i + 1) и выполняй условие1,
в противном случае - если условие i < n FALSE (т.е. i =n ) - рекурсия останавливается и алгоритм выдаёт результат FALSE.

Казалось бы всё просто-если существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к массиву А , так что-бы сумма всех чисел вышеуказанной группы=m, то алгоритм обязательно это выявит и выдаст результат TRUE - но вся проблема в том как заставить алгоритм "добросовестно" проверять условие1.
Я составил схему выполнения условия1 -устанавливающую порядок по которому будет происходить проверка всех возможных групп разных целых чисел ,каждая из которых является в свою очередь подмножеством к массиву A[i+1,...,n], пока не будет выявлена такая группа чисел что-бы сумма всех её чисел =m-A[ i ](разумеется если такая группа чисел существует)
В этой схеме i=1, n=8, элементы массива пронумерованны от 1 до 8.
Но вывести рекурсивный алгоритм по этой схеме не удалось:( - какое ваше мнение форумчане:???:
Может быть не возможно вывести рекурсивный алгоритм по этой схеме:-? и нужно искать другой путь решения:???:

схема выполнения условия1:
1-> 2 ->3-> 4 ->5-> 6-> 7 ->8
1 ->2-> 3-> 4-> 5-> 6-> 8
1-> 2-> 3-> 4-> 5-> 7-> 8
1-> 2-> 3-> 4-> 5-> 8

1-> 2-> 3-> 4-> 6-> 7-> 8
1-> 2-> 3-> 4-> 6-> 8
1-> 2-> 3-> 4-> 7-> 8
1-> 2-> 3-> 4-> 8

1-> 2-> 3-> 5-> 6-> 7-> 8
1-> 2-> 3-> 5-> 6-> 8
1-> 2-> 3-> 5-> 7-> 8
1-> 2-> 3-> 5-> 8
1-> 2-> 3-> 6-> 7-> 8
1-> 2-> 3-> 6-> 8
1-> 2-> 3-> 7-> 8
1-> 2-> 3-> 8

1-> 2-> 4-> 5-> 6-> 7-> 8
1-> 2-> 4-> 5-> 6-> 8
1-> 2-> 4-> 5-> 7-> 8
1-> 2-> 4-> 5-> 8
1-> 2-> 4-> 6-> 7-> 8
1-> 2-> 4-> 6-> 8
1-> 2-> 4-> 7-> 8
1-> 2-> 4-> 8
1-> 2-> 5-> 6-> 7-> 8
1-> 2-> 5-> 6-> 8
1-> 2-> 5-> 7-> 8
1-> 2-> 5-> 8
1-> 2-> 6-> 7-> 8
1-> 2-> 6-> 8
1-> 2-> 7-> 8
1-> 2-> 8

1-> 3-> 4-> 5-> 6-> 7-> 8
1-> 3-> 4-> 5-> 6-> 8
1-> 3-> 4-> 5-> 7-> 8
1-> 3-> 4-> 5-> 8
1-> 3-> 4-> 6-> 7-> 8
1-> 3-> 4-> 6-> 8
1-> 3-> 4-> 7-> 8
1-> 3-> 4-> 8
1-> 3-> 5-> 6-> 7-> 8
1-> 3-> 5-> 6-> 8
1-> 3-> 5-> 7-> 8
1-> 3-> 5-> 8
1-> 3-> 6-> 7-> 8
1-> 3-> 6-> 8
1-> 3-> 7-> 8
1-> 3-> 8

1-> 4 ->5 ->6 ->7-> 8
1-> 4 ->5-> 6 ->8
1-> 4 ->5-> 7-> 8
1 ->4 ->5 ->8
1 ->4-> 6-> 7-> 8
1-> 4-> 6-> 8
1-> 4-> 7-> 8
1-> 4-> 8

1-> 5-> 6-> 7-> 8
1-> 5-> 6-> 8
1-> 5-> 7-> 8
1-> 5-> 8

1-> 6-> 7-> 8
1-> 6-> 8

1-> 7-> 8

1-> 8

Я особо не вчитывался в сообщения выше, поэтому заранее прошу прощения, если моё предложение будет уже вне потребности. Итак, есть так называемый алгоритм Свине-Харта ( по имени, кажется, двух учёных, Swine-Heart algorithm). Он был опубликован в 70-х годах в одной из научных статей и взбудоражил всю комбинаторную научную общественность. Он решал не конкретно вашу задачу, Bagira, а немного другую. Есть число m, дан массив, в котором, однако, могут встречаться повторяющиеся числа. Все числа полагаются натуральными. Спрашивается : сколькими разными способами можно разложить число m в линейную комбинацию из элементов массива с натуральными коэффициентами ? То есть : m = сумма из чисел, каждое из которых есть число из массива, домноженное на некоторое произвольное неотрицательное целое. Например, для числа m=6 и массива ( 2, 3 ) только две возможности : 6 = 2*3 +3*0 и 6 = 2*0 +3*2; для числа 7 и массива ( 3, 2, 8 ) одна возможность : 7 = 3*1+2*2+8*0; для числа 1234 и массива ( 100, 679, 23 ) вообще нет возможностей. А вот для 10 и ( 5, 5 ) три возможности : 10 = 5*2+5*0 , 5*0+5*2 и 5*1+5*1. Актуальность этой задачи более чем очевидна. Например, в экономике - для конкретных стоимости и набора монет посчитать количество возможных разложений данной стоимости в накопления только из монет данного типа. При этом совпадающие по ценности ( но не физически ) монеты не отождествляются. Другое применение - в химии. Там даются какие-то уровни энергии и распределения по этим уровням электронов. До появления алгоритма Свине-Харта все машины просто зависали на переборных алгоритмах, когда попадались ( а в реальной жизни только так и бывает ) большие числа m и длинные массивы из малых чисел. Гениальный Свине-хартовский алгоритм, мягко говоря, сделал переворот. В общем, довольно философии. Я готов, если хотите, прислать сишный код этого алгоритма, он занимает всего лишь 15 строчек ( !!! ). Физический смысл его работы на данный момент вам объяснить не смогу, так как ознакомился я с ним около двух лет назад и сейчас ничего не помню. Знаю только, что он использует всего лишь двойной цикл. И всё ! Хотя и называется рекурсивным ( так как подсчитывает для меньших чисел m ), самой рекрсии в коде он не использует. Цель алгоритма - представить именно число комбинаций, а не их сами. Это недостаток алгоритма ( надеюсь, без проблем устранимый ).
Если посмотреть на вашу задачу, то на вопрос о существовании этот алгоритм в некоторых случаях может ответить : в случае остутствия суммы получится ноль как в первой, так и во второй задаче. Связь с первой задачей теряется, если в существующем разложении есть коэффициенты большие 1. В общем, про связь с вашей задачей однозначно сказать что-то определённое пока трудно. Но, возможно, алгоритм будет полезен, если его чуть модифицировать под вашу задачу.



Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means !

Спасибо Saha за отклик!
Я лично , а также другие участники этой темы, будут благодарны вам за публикацию сишного кода этого алгоритма.

Всё-таки напишу полностью программку с оценкой времени O(m*n).

// Исходные данные:
int m, n;
a - массив размера n;

// Вспомогательные переменные:
ls - массив размера m+1 (индекс может быть от 0 до m);
int i, k; // счётчики в a и ls, соответственно

// Роль массива ls ("last summand"):
// в каждый момент ls[k] есть последнее слагаемое в разложении k
// либо 0, если для k не нашли разложения

// Основная часть:
ls[0] = -1; // 0 можно разложить (в пустую сумму), поэтому ls[0]<>0
for (i = 0; i < n; i++)
{
int x = a[ i ];
for (k = m; k >= x; k--)
if (ls[k] == 0 && ls[k - x] != 0)
ls[k] = x;
}

// Выдача ответа
if (ls[m] == 0) { выдать "нет решений" и выйти; }
for (k = m; k > 0; k -= ls[k]) выдать ls[k];

Замечание 1. С помощью ещё одного массива можно считать число всевозможных разложений.

Замечание 2. Если сначала отсортировать массив a по убыванию, то получится оптимальное решение по числу слагаемых (так как предпочтение отдаётся первым элементам массива a).

Цитата

maxal писал(а) :
Пусть u и v - коэффициенты Безу для A и B, т.е. такие целые числа что НОД(A,B) = 1 = uA + vB.

Интересно, а насколько принято выражение "коэффициенты Безу"? В каких учебниках так говорится? Я чаще слышал "линейное представление НОД", но это нехорошо.

Возможно, maxal, мы друг друга не поняли. Если вы говорите правду, тогда я одного не пойму : насколько тёмными были люди науки всего мира, использовавшие експоненциальные переборные алгоритмы на старых процессорах, вместо того, чтобы не использовать стариков Евклида и Безу. А код я уже отправил Bagira на e-mail. С некоторыми пояснениями. Красота алгоритма в том, что индексы элементов массива активно используются в вычислениях с самими значениями этих элементов. Причём важно, как пронумерован массив ( надо с единицы, а не с нуля ). В Безу было нечто подобное ? Здесь публикую код, но без пояснений. Извините за халтуру с точки зрения проф. программирования.

#include<stdio.h>
#include<stdlib.h>

long * count(int *,int, int);

void main()
{
int i,m,k,*c; long *p;
printf("Input m :\nm =");
scanf("%d",&m);
printf("Input the length of the array :\nk =");
scanf("%d",&k);
c=(int *)malloc((k+1)*sizeof(int));
printf("Finally, input the elements of the array :\n");
for(i=1;i<k+1;i++)
{
printf("c[%d] =",i);
scanf("%d",&c[i ]);
}
p=count(c,k,m);
for(i=1;i<m+1;i++)
{
if((i-1)%5==0) printf("\n");
printf("p[%d] =%ld ",i,p[i ]);
}
printf("\n");
}

long * count(int *c, int k, int m)
{
int i,l,j, j1, j2; long *p;
p=(long *)malloc((m+1)*sizeof(long));
for(i=1;i<m+1;i++) p[i ]=0;
for(i=1;i<k+1;i++)
{
j=c[i ]; j1=j+1; p[j]++;
for(l=j1;l<m+1;l++)
{
j2=l-j; p[l]=p[l]+p[j2];
}
}
return p;
}



Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means !