Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Задача разбиения множества на две группы с равной суммой
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
_Haron_ _Haron_ вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 09.02.2006
По умолчанию Задача разбиения множества на две группы с равной суммой - 09.02.2006, 12:19

Помогите с задачей: есть набор положительных целых чисел. Надо составить алгоритм разбиения этих чисел на две группы с равной суммой или доказать что при данном наборе чисел такое разбиение невозмжно
Ответить с цитированием
  (#2 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 09.02.2006, 12:54

Задача сводится к задаче поиска эллементов, сумма которых составляет S/2 (если S - сумма исходной последовательности).

Первое решение, которое придумалось, оказалось на Прологе.
Если Вы знаете Пролог, легко разберетесь, если нет, переведу на что-нибудь более конвенциональное.

Код:
task(L,L2,L3):-sum_list(L,S),S1 is S/2,f1(L,S1,L2,L3).

sum_list([],0).
sum_list([X|Xs],S):-sum_list(Xs,S1),S is S1+X.

f1([X|Xs],X,[X],Xs):-!.
f1([X|Xs],S,[X|L],L1):-X<S,S1 is S-X,f1(Xs,S1,L,L1).
f1([X|Xs],S,L,[X|L1]):-f1(Xs,S,L,L1).
Ответить с цитированием
  (#3 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 09.02.2006, 20:18

Пролог я не знаю, но алгоритм формулирую (если он полностью совпадает с Вашим, прошу извинить):
1)Найти сумму чисел. Разделить ее на два.
2)Если результат не целый, значит невозможно.
3)Если целый, полным перебором перебрать все комбинации чисел, проверяя каждое разбиение.
Ответить с цитированием
  (#4 (permalink)) Старый
_Haron_ _Haron_ вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 09.02.2006
По умолчанию 10.02.2006, 03:10

хм..спасибо конечно =)
но...то что вы написали это и так понятно...
полным перебором можно только при малом количестве чисел
а если их например уже больше 30 то у меня паскаль на 4 пне уже третий час сейчас считает все возможные переборы =)
хотелось бы более простого и оптимального алгоритма
Ответить с цитированием
  (#5 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 10.02.2006, 04:31

Цитата:
Originally posted by _Haron_
[b]то у меня паскаль на 4 пне уже третий час сейчас считает все возможные переборы =)
Считает, или просто висит?
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 10.02.2006, 05:34

Перебор-то всё равно будет полный (а как иначе убедиться, что решения нет?), разве что повторения лишние можно убрать. Как вариант:
Код:
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

typedef vector<int>::iterator VI;

bool findsum(VI cur, VI end, int s, int sum)
{
    if (s == sum) return true;
    if (s > sum) return false;
    while (cur != end)
    {
        if (findsum(cur+1, end, s+*cur, sum)) return true;
        rotate(cur, cur+1, end--);
    }
    return false;
}

void main()
{
    ifstream in("numbers.in");
    ofstream out("numbers.out");
    vector<int> val;
    int a, vsum = 0;

    while (in >> a) val.push_back(a), vsum += a;
    if ((vsum & 1) || !findsum(val.begin()+1, val.end(), val[0], vsum/2)) out << "NO";
    else
    {
        int i, sum = 0;
        for (i = 0; sum < vsum/2; sum += val[i++]) out << val[i] << " ";
        out << endl;
        while (i < val.size()) out << val[i++] << " ";
    }
}
В файле numbers.in - через пробел исходные числа, в файле numbers.out - на двух строках полученное разбиение или NO, если его не существует.

(Для 30 чисел при отсутствии решения считает примерно 15 секунд.)
Ответить с цитированием
  (#7 (permalink)) Старый
_Haron_ _Haron_ вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 09.02.2006
По умолчанию 10.02.2006, 16:00

michael, спасибо
но я к сожалению не знаю С
ты не мог бы написать тот же алгоритм на паскале?
Ответить с цитированием
  (#8 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 10.02.2006, 16:45

На Паскале писать не хочу. Алгоритм следующий:
Складываем числа из массива по-порядку (в рекурсивной функции для обработки всех вариантов). Если получается равенство с общей полусуммой, переход на вывод результатов. Если полусумма не достигается для всех вариантов с некоторым элементом, то перестановкой (у меня вращением, но это не обязательно, можно просто перестановкой с текущим последним элементом - получится быстрее) отправляем этот элемент в конец массива, и далее его не рассматриваем (уменьшаем кол-во элементов в массиве). Продолжаем до тех пор, пока не дойдём до конца массива (с учётом указанного уменьшения), после чего возвращаемся на предыдущую итерацию для отбрасывания очередного элемента. В итоге, если равенство с полусуммой достигнуто, оно достигается на первой половине (половина - условно) массива.
Немного корявое описание, в исходнике всё красивее.
Ответить с цитированием
  (#9 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,994
Сказал(а) спасибо: 2
Поблагодарили 307 раз(а) в 307 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 11.02.2006, 17:54

Как всё запущено!
Обсуждаемая Вами задачи является классическим представителем NP-полных задач. => решения нет, кроме полного перебора.
Мой совет - ищите эвристики.
Мой второй совет - подождите апреля, выйдет журнал "Информационные технологии". Там будет статья про то, как решать такие задачи и вообще про то, как АВТОМАТИЗИРОВОННО находить стоящие эвристики для NP-задач.
Ответить с цитированием
  (#10 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию Re: Задача разбиения множества на две группы с равной суммой - 11.02.2006, 22:48

Винитарх, все не так уж запущено, Вы просто невнимательно прочитали условие:
Цитата:
Originally posted by _Haron_
[b]доказать что при данном наборе чисел такое разбиение невозмжно
Эвристики помогли бы быстрее найти решение (если оно есть), но при такой постановке задачи от полного перебора не уйти...
Ответить с цитированием
  (#11 (permalink)) Старый
_Haron_ _Haron_ вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 09.02.2006
По умолчанию 12.02.2006, 15:25

хорошо..предлагайте тогда варианты полного перебора
вот мой вариант
Код:
for j:=1 to 536870911
do begin
         i:=30;
         while ar[i]=1
         do begin
                ar[i]:=0;
                dec(i);
             end;
         ar[i]:=1;   
       end; {генерация всех 01 наборов для 30 переменных}
а потом...
Код:
          sum:=0;
          for k:=1 to n do
          begin
               a:=ar[k]*vxod[k];
               Sum:=Sum+a;
          end;
         if sum=s/2 then
                   Write('yra'); {считаем в цикл сумму для каждого
                                        01 набора (vxod это массив наших чисел) 
                                        и проверяем условие}
Но мне такой вариант не нравится потому что для каждого набора сумма потом считается в цикле а это очень замедляет работу
вся эта штука работает 5 минут при отсутствии решения
Может как то можно считать сумму уже при генерации наборов?
я пока что не могу придумать
Если кто знает напишите...
спасибо

/* M: Не стесняемся использовать BBcode! S. */
Ответить с цитированием
  (#12 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 13.02.2006, 02:10

Цитата:
Originally posted by _Haron_
[b]хорошо..предлагайте тогда варианты полного перебора
В чём проблема-то с рекурсией?
Мысли у тебя правильные. Сумму каждый раз пересчитывать не нужно. Рекурсивный вызов этот недостаток как раз и устраняет (наверное, можно и без рекурсии, но это сложнее). А так - тот же перебор. В результате оптимизированный вариант выполняется за 5 секунд для 30 чисел при отсутствии решения (ввод/вывод аналогично предыдущему варианту):
Код:
#include <fstream>
#include <algorithm>

using namespace std;

int val[256];

bool findsum(int cur, int end, int s, int sum)
{
    if (s == sum) return true;
    if (s > sum) return false;
    while (cur < end)
    {
        if (findsum(cur+1, end, s+val[cur], sum)) return true;
        end--;
        swap(val[cur], val[end]);
    }
    return false;
}

void main()
{
    ifstream in("numbers.in");
    ofstream out("numbers.out");
    int a = 0, vsum = 0;

    while (in >> val[a]) vsum += val[a++];
    if ((vsum & 1) || !findsum(1, a, val[0], vsum/2)) out << "NO";
    else
    {
        int i = 0;
        for (int sum = 0; sum < vsum/2; sum += val[i++]) out << val[i] << " ";
        out << endl;
        while (i < a) out << val[i++] << " ";
    }
}
Функция поиска решения (findsum) в Паскаль переводится практически дословно. Разбирайся.
Кстати, если ты используешь Borland Pascal 7.0, то тормозить может в том числе и из-за него, он компилирует неэффективный 16-битный код, что особенно пагубно на P4 (Athlon и P3 легче его переносят). У меня были случаи до 20 раз медленнее работали практически одинаковые программы (по сравнению с VC++ 7.1).

P.S. Теоретический предел полного перебора при 30 числах - 0,7 секунды в пустом цикле (на моём компьютере, конечно же). Так что 5 секунд, по-моему, очень хороший результат.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача на множества:определить симметричную разность множеств aska666 Prolog 2 22.04.2012 09:27
Найти строки с суммой елементов меньшей 100 Annetka Visual Basic 0 09.04.2011 16:29
Поиск кол-ва строк с одинаковой суммой элементов ex-frontal Pascal 2 06.01.2011 15:10
множества гидрохоботан Pascal 1 29.11.2010 11:59
Написать программу чтобы выводила размещения с повторениями с суммой значений Irishka_899 Вопросы начинающих программистов 2 14.10.2010 11:19
Нахождение столбца с наибольшей суммой элементов в матрице Borland C++Builder 6 SERG29 Вопросы начинающих программистов 0 03.04.2008 10:39
исследование стратегии поиска минимального разбиения Парамонов Задания за деньги 1 16.12.2007 21:12
Алгоритм разбиения на подмножества ребер в заданном графе на C++ Верочка Вопросы начинающих программистов 1 13.12.2007 14:59
Создание группы Anonimizer_me Некоммерческие проекты 5 02.06.2006 14:29
Поиск пути с максимальной суммой в матрице в C++ Atma Вопросы начинающих программистов 0 29.05.2006 22:31
Множества BelVik Prolog 1 08.06.2005 11:08
Задача на множества требуется помощь в решении emm Pascal 4 13.11.2004 02:26



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов