Как разбить множество на три подмножества с одинаковой суммой элементов?

Question

[Ашот Такиев]

Добрый день.

Встретилось задание из раздела о динамическом программировании, которое вызывает у меня трудности. Необходимо построить алгоритм, который по заданному множеству определяет, можно ли его разбить на три части, в которых суммы всех элементов будут равны. Например:
[1, 2, 3, 4, 4, 5, 8] -> {1,8}, {4,5}, {2,3,4}

Очевидно, что если сумма всех элементов не делится на 3, то множество не содержит такого разбиения (самая простая часть:) ). Но как действовать дальше? Вроде как мы должны проверять, к какому подмножеству у нас относится a_i элемент.
Но все это формализовать и прикрутить динамику не получается.
Буду признателен, если сможете направить на истинный путь.

Comments

[Олег Цилюрик]

У вас условие задачи неточно сформулировано. В вашем примере [1, 2, 3, 4, 4, 5, 8] - это не множество (set), а
multiset.

Answer 1

[Mrrl]

Задача о рюкзаке, даже о двух :)
Заводите массив M[0..S/3,0..S/3] (можно битовый, но лучше побольше - чтобы хранить обратные ссылки). В нём будут отмечены элементы M[a,b], такие, что из уже просмотренных элементов текущего набора можно выбрать непересекающиеся подмножества с суммами a и b.
Когда приходит очередной элемент x - выполняете M[a,b]=M[a,b] | M[a-x,b] | M[a,b-x] для всех a,b начиная с конца (с больших a,b). Если при этом 0 сменился на 1 - помечаете в массиве обратных ссылок, из какого элемента вы сюда попали.
Сложность - O(n*S^2). Можно ли сделать лучше, не знаю.

Вот вариант кода - но он печатает только два множества. Как напечатать третье, разберётесь.

spoiler

static void Main(string[] args) {
            int[] dat=Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
            int S=0;
            foreach(int x in dat) S+=x;
            if(S%3!=0) {
                Console.WriteLine("-1"); return;
            }
            S/=3;
            int[,] M=new int[S+1,S+1];
            M[0,0]=-1;
            foreach(int x in dat) {
                for(int a=S;a>=0;a--) {
                    for(int b=S;b>=0;b--) {
                        if(M[a,b]==0) {
                            if(a>=x && M[a-x,b]!=0) M[a,b]=x;  // back by set1
                            else if(b>=x && M[a,b-x]!=0) M[a,b]=-x;  // back by set2
                        }
                    }
                }
            }
            if(M[S,S]==0) {
                Console.WriteLine("-1"); return;
            }
            int u=S,v=S;
            string res1="",res2="";
            while(u!=0 || v!=0) {
                if(M[u,v]>0) {
                    res1+=" "+M[u,v]; u-=M[u,v];
                } else {
                    res2+=" "+(-M[u,v]); v+=M[u,v];
                }
            }
            Console.WriteLine(res1);
            Console.WriteLine(res2);
        }

Comments

[Ашот Такиев]

Спасибо вам за совет! Вроде как разобрался, дополнительно используя описание проблемы о разбиении. А разве не получится без использования дополнительного массива prev восстановить ответ? Ведь у нас же есть последовательности в массиве M[n, S, S] для элементов, которые входят либо в разбиение S1, либо в S2. Просто их вычеркиваем из входного массива, получаем два разбиения, а оставшееся разбиение - то что осталось. )

[Mrrl]

Ашот Такиев: Если получится восстановить, то хорошо. Но всё зависит от того, что именно вы храните в массиве. Если это, допустим, история заполнения достижимых ячеек (sum(S1),sum(S2)), то при обратном поиске есть опасность пойти по ложному пути.
Массив обратных ссылок - самый дешёвый и надёжный вариант. И его можно делать не дополнительным, а единственным (ссылки нет - клетка пока недостижима).

[Владимир Петриго]

Mrrl: Мне кажется можно немного модифицировать вашу последовательность решения. Массив M сделать трехмерным M[0...n][0...S/3][0...S/3] и каждый уровень будет определять, какие суммы достижимы для множества из i элементов (т.е. первый индекс указывает число доступных элементов A[0...i]). А в конце, если разбиение существует (т.е. M[n][S/3][S/3] = 1), мы встаем на данный элемент и в обратном порядке восстанавливаем каждое разбиение.

[Mrrl]

Владимир Петриго: Да, если на обратном пути проверять именно возможность прохода по последнему элементу, то не заблудимся. Будет ли проще решение? Возможно, будет. Хотя и незначительно.
А если последовательность содержит меньше 40 элементов, то можно сделать наоборот - завести массив UInt64[S/3+1,S/3+1], и сразу накапливать в его посещённых элементах разбиение на подмножества - в троичной системе. Тогда идти назад не придётся, в последней клетке будет сразу готов ответ.

[Владимир Петриго]

Mrrl: да. Все зависит от входных условий. =)

[Mrrl]

Вики утверждает, что достаточно O(n*m^2) памяти, где m - наибольшее число, а n - длина последовательности. Это заметно меньше, чем O(S^2). Интересно, как.

[Владимир Петриго]

Ну можно извернуться и не использовать матрицу размера S/3 * S/3, так как относительно главной диагонали значения обновляются симметрично.

[Mrrl]

Владимир Петриго: Это даст выигрыш в 2 раза. При больших n (и не очень больших значениях) этого не хватит.

[volyihin]

Mrrl а не подскажете для чего мы записываем отрицательные элементы?
M[a,b]=-x; // back by set2

И восстанавливаем тоже отрицательные. Для чего это нужно?

[Mrrl]

volyihin: В знаке закодировано направление, с которого мы пришли в клетку (a,b): если в ней +x, то пришли с клетки (a-x,b) - и элемент x принадлежит первому множеству, а если -x - то пришли с (a,b-x), и элемент x принадлежит второму множеству.

Answer 2

[Антон Федорян]

Внимательно читайте про разбиения. Зачем мудрить.

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

#x = [1, 2, 3, 4, 4, 5, 8]
#x = [5, 7, 12, 3, 3, 1, 5]
x = [123, 1, 8, 4, 120, 59, 59, 10]

if (sum(x) % 3 == 0):
	tmp = sum(x) / 3
	x.sort()
	x.reverse()
	for i in range(3):
		y = []
		j = 0
		while (sum(y) != tmp):
			if ((sum(y) + x[j]) <= tmp):
				y.append(x[j])
				del(x[j])
			else:
				j += 1
		print(y)
else:
	print('Вознеможно разбить на 3 равные части!')

Comments

[Mrrl]

Вы решили задачу о рюкзаке за O(N)? Поздравляю.
И что она сделает с таким массивом: [3, 2, 2, 3, 2, 6] ?

[Антон Федорян]

Mrrl: что и должна по условию
6
3, 3
2, 2, 2

[Антон Федорян]

Можно проверить результаты здесь

[Mrrl]

Антон Федорян:
x = [8, 6, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3]
IndexError: list index out of range

Answer 3

[Олег Цилюрик]

Но как действовать дальше?

Какой-то рекурсивный алгоритм, где:
1. набираем элементы до суммы S/3 в 1-е множество ...
2. для каждой найденной комбинации п.1 набираем элементы до суммы S/3 в 2-е множество ...
3. смотрим равна ли сумма того, что осталось S/3?
Дерево поиска.
Как вы не мудрите, итоговое решение будет вариантом такого.
Можно придумать что-то из жадных алгоритмов, чтобы сразу не углубляться в рекурсию на всю глубину.

Хорошая задача ...
Но громоздкая, поэтому сюда не помещаю.
Вот вариант решения: примеры задач при изучении C++

$ ./3set
Вводите числа построчно (пустая строка - конец ввода):
1 2 3 4
4 5 8

{ 1, 2, 3, 4, 4, 5, 8 } ->
{ 1, 8 }
{ 4, 5 }
{ 2, 3, 4 }

Answer 4

[Alex]

Решил как смог )

function summ(a){
 if(a.length==0){return 0}
 else{res = 0; for(var i=0;i<a.length;i++){res=res+a[i]} return res;}
}
 var ar = [5, 7, 12, 3, 3, 1, 5]; 
ar=ar.sort(function(a, b){return a-b}); 
var b=[];
var c =[];
 var d=[]; 
for(var i=ar.length-1;i>-1;i--){
if(summ(b)+ar[i]<=summ(ar)/3) {b.push(ar[i])}
else if(summ(c)+ar[i]<=summ(ar)/3) {c.push(ar[i])}
else if(summ(d)+ar[i]<=summ(ar)/3) {d.push(ar[i])}}; 
console.log(b);console.log(c);console.log(d)

Чет мне кажется что не всегда будет работать)