разделить элементы данного массива на три подмассива с одинаковой суммой элементов - Помощь студентам

astr_al · 19.12.2009, 02:10

Здравствуйте, требуется помощь любая, от кода ( Си или паскаль, не важно, но лучше первое) до просто словесного описания алгоритма.Заранее спасибо.Вот условие:

Дан одномерный массив натуральных чисел. Выяснить, можно ли разделить элементы данного массива на три подмассива с одинаковой суммой элементов. Если можно, то вывести
а) одно решение;
б) все решения.

astr_al · 19.12.2009, 12:30

Есть у кого-нибудь мысли?

m0nax · 19.12.2009, 17:37

а если просто выяснить сумму всех элементов и разделить на 3, если получилось без остатка значит делится, если с остатком значит не делится?

или же не обязательно использовать именно все элементы массива?

Анатоль · 19.12.2009, 20:05

Пункт а) решается простой динамикой.
Ты находишь какую тебе сумму надо набрать(сумма всех элементов делить на 3).
Потом пытаешься набрать эту сумму.
Проще всего это делать с помощью рюкзака, но обьяснять как он работает сложно, поэтому дам ссылку.
http://informatics.mccme.ru/moodle/m...5&chapterid=60
Когда удалось набтаь эту сумму, то выкидываешь использованные элементы из массива и делаешь ещё раз.

19.12.2009, 02:10	#1
astr_al Регистрация: 28.04.2009 Сообщений: 3	разделить элементы данного массива на три подмассива с одинаковой суммой элементов Здравствуйте, требуется помощь любая, от кода ( Си или паскаль, не важно, но лучше первое) до просто словесного описания алгоритма.Заранее спасибо.Вот условие: Дан одномерный массив натуральных чисел. Выяснить, можно ли разделить элементы данного массива на три подмассива с одинаковой суммой элементов. Если можно, то вывести а) одно решение; б) все решения.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
максимальная сумма элементов подмассива в массиве	Sparky	Помощь студентам	11	05.11.2009 15:50
найти подпоследовательность из подряд идущих элементов с наибольшей суммой на С++	aj_tramp	Помощь студентам	2	12.12.2008 08:57
Расположить элементы массива в порядке убывания частоты встречаемости элементов.	QWERT12345	Паскаль, Turbo Pascal, PascalABC.NET	7	14.11.2008 22:30
Разделить строку на три столбца	инженер	Microsoft Office Excel	10	01.02.2008 04:58

19.12.2009, 12:30	#2
astr_al Регистрация: 28.04.2009 Сообщений: 3	Есть у кого-нибудь мысли?

19.12.2009, 17:37	#3
m0nax Форумчанин Регистрация: 25.09.2009 Сообщений: 525	а если просто выяснить сумму всех элементов и разделить на 3, если получилось без остатка значит делится, если с остатком значит не делится? или же не обязательно использовать именно все элементы массива?

19.12.2009, 20:05	#4
Анатоль Пользователь Регистрация: 17.12.2009 Сообщений: 74	Пункт а) решается простой динамикой. Ты находишь какую тебе сумму надо набрать(сумма всех элементов делить на 3). Потом пытаешься набрать эту сумму. Проще всего это делать с помощью рюкзака, но обьяснять как он работает сложно, поэтому дам ссылку. http://informatics.mccme.ru/moodle/m...5&chapterid=60 Когда удалось набтаь эту сумму, то выкидываешь использованные элементы из массива и делаешь ещё раз.