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

Автор темы cantyman67 (Bagira) 
ОбъявленияПоследний пост
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеМатематики, программисты, репетиторов (платформа SapioX)28.01.2021 12:47
ОбъявлениеАктуарий в PPF Life Insurance (Junior)25.03.2021 21:35
20.06.2005 18:19
Рекурсивный алгоритм, определяющий группу чисел из массива, чтобы сумма=m
Не удаётся вывести правильный алгоритм для такой задачи:
дано- массив целых чисел , величина массива=n и целое число m.
требуется -создать рекурсивный алгоритм котораый бы определял: или существует группа чисел являющаяся подмножеством к данному массиву, так что бы сумма этих чисел=m.
Мне важен сам алгоритм, т.к. если он составлен правильно то написание программы - дело техники.
20.06.2005 23:27
Можно более детальней условие?
что бы сумма=m



Исчу бессрочно книги и лекции по математике (матстатистика, оптимизация...)
21.06.2005 00:58
Рекурсивный алгоритм, определяющий группу чисел из массива, что бы сумма=m
Более детальное условие задачи:
1) дан массив разных целых чисел<=>т.е. конечное множество целых чисел которые расположены в определённой последовательности. (например: A={5,3,11,2,8,6,15,4}, в массиве A , 5 расположен на 1_ой
позиции, 11 на 3_ой позиции, 4 на 8_ой позиции)
2) величина массива=n (целое число), т.е. n - количество членов множества. (например: для A={5,3,11,2,8,6,15,4} , n=8)
3) дано целое число m.

цель задачи: создать рекурсивный алгоритм который бы выявлял или существует хотя-бы одна группа разных целых чисел , которая является в свою очередь подмножеством к данному множеству, так что-бы сумма всех чисел вышеуказанной группы=m.
21.06.2005 10:58
Это разве делается как-то проще, чем полным перебором? (-)
21.06.2005 11:47
Есть алгоритмы сложности m*n и 2^n
Похоже, для небольших m напрашивается алгоритм сложности m*n.

Завести массивы s[m+1] и last_summand[m+1]:
s[k] - число слагаемых, которыми можно представить число k.
last_summand[k] - последнее слагаемое в разложении k.

Устроить большой цикл по исходным числам и "добавлять возможные суммы". Внутри большого цикла - вложенный цикл по массиву s, отсюда сложность m*n. После завершения работы большого цикла ответ строится по массиву last_summand не более чем за n шагов.

Конечно, можно обойтись без вспомогательных массивов и всё сделать рекурсивно. Тогда получается алгоритм сложности 2^n.

P. S. Хотелось минимизировать число слагаемых, но не могу сообразить, как это правильно сделать.

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

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

25.06.2005 13:35
создание алгоритма
Цитата

egor писал(а) :
Похоже, для небольших m напрашивается алгоритм сложности m*n.

Завести массивы s[m+1] и last_summand[m+1]:
s[k] - число слагаемых, которыми можно представить число k.
last_summand[k] - последнее слагаемое в разложении k.

Устроить большой цикл по исходным числам и "добавлять возможные суммы". Внутри большого цикла - вложенный цикл по массиву s, отсюда сложность m*n. После завершения работы большого цикла ответ строится по массиву last_summand не более чем за n шагов.

Конечно, можно обойтись без вспомогательных массивов и всё сделать рекурсивно. Тогда получается алгоритм сложности 2^n.

P. S. Хотелось минимизировать число слагаемых, но не могу сообразить, как это правильно сделать.

Спасибо egor!
Я думаю что минимизировать число слагаемых при итеративном решении вышеуказанной задачи - можно, если использовать стэк вместо вспомогательных массивов.
Конечно было бы здорово egor -если вы изложите более подробно ваш алгоритм-тогда сообща можно найти решение.

25.06.2005 16:49
Составление алгоритма
Цитата


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"?

25.06.2005 17:28
разъяснения
Цитата

Bagira писал(а) :
1)что такое NP-полная задача?
Грубо говоря, такая, для которой не существует алгоритма, решающего ее за полиномиального от длины входа время (принимая на веру неравенство P <> NP). Другими словами, коль скоро входные данные для этой задачи будут "большими", найти точное решение за обозримое время будет невозможно.

Цитата

2)что имеется в виду под выражением:"Даже в таком частном случае: m = сумма всех чисел массива / 2"?
Это задача "располовинивания" данного массива. Дан массив чисел, сумма которых равна S. Нужно определить можно ли из этого массива выбрать некоторые элементы так, чтобы их сумма равнялась S/2.

Цитата

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

25.06.2005 18:00
составление алгоритма
Ещё раз хочу поблагодарить вас 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

25.06.2005 21:38
Сумма из одного слагаемого допускается?
Сначала я почему-то подумал, что запрещено раскладывать m в сумму, состоящую из одного слагаемого. Если сумма из одного слагаемого допускается, то решение совсем простое: либо вспомогательный массив размера m и двойной цикл (сложность n*m), либо рекурсия (сложность 2^n). Для минимизации числа слагаемых достаточно отсортировать исходный массив.

04.07.2005 22:42
А это поможет ?..
Я особо не вчитывался в сообщения выше, поэтому заранее прошу прощения, если моё предложение будет уже вне потребности. Итак, есть так называемый алгоритм Свине-Харта ( по имени, кажется, двух учёных, 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 !
04.07.2005 23:05
Swine-Heart algorithm ?
Цитата

Saha писал(а) :
Я особо не вчитывался в сообщения выше, поэтому заранее прошу прощения, если моё предложение будет уже вне потребности. Итак, есть так называемый алгоритм Свине-Харта ( по имени, кажется, двух учёных, Swine-Heart algorithm).

Не могли бы Вы уточнить название алгоритма, а то гуглу "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.

Странно, что он мог кого-то там "взбудоражить". Эта задача легко решается с помощью соотношения Безу и расширенного алгоритма Евклида.

Цитата

Я готов, если хотите, прислать сишный код этого алгоритма, он занимает всего лишь 15 строчек ( !!! ).

Приведите код прямо здесь. Заранее спасибо.
05.07.2005 00:02
Свине-хартовский алгоритм
Спасибо Saha за отклик!
Я лично , а также другие участники этой темы, будут благодарны вам за публикацию сишного кода этого алгоритма.
05.07.2005 00:17
Swine-Heart algorithm ?
Цитата

Странно, что он мог кого-то там "взбудоражить". Эта задача легко решается с помощью соотношения Безу и расширенного алгоритма Евклида.

Не могли бы вы maxal привести более подробное решение этой задачи с помощью "соотношения Безу и расширенного алгоритма Евклида".

Заранее благодарен.
05.07.2005 00:49
Решение исходной задачи (сложность m*n)
Всё-таки напишу полностью программку с оценкой времени 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).

05.07.2005 02:17
число решений m=x*A+y*B
Расскажу про случай двух взаимно-простых чисел A и B.

Пусть u и v - коэффициенты Безу для A и B, т.е. такие целые числа что НОД(A,B) = 1 = uA + vB.
Причем без потери общности можно считать, что 0 < u < B и -A < v < 0. Коэффициенты Безу вычисляются с помощью расширенного алгоритма Евклида.

Тогда число решений диофантова уравнения m=xA+yB в целых неотрицательных числах равно floor(um/B) - ceil(-vm/A) + 1.

05.07.2005 11:59
Вопрос по терминологии: "коэф-ты Безу"
Цитата

maxal писал(а) :
Пусть u и v - коэффициенты Безу для A и B, т.е. такие целые числа что НОД(A,B) = 1 = uA + vB.
Интересно, а насколько принято выражение "коэффициенты Безу"? В каких учебниках так говорится? Я чаще слышал "линейное представление НОД", но это нехорошо.
05.07.2005 12:39
ответ по терминологии
06.07.2005 00:52
Отправил
Возможно, 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 !
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти