Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 02.03.2010, 18:05
Новичок

Отправить личное сообщение для jura Посмотреть профиль Найти все сообщения от jura
 
Регистрация: 02.03.2010
Сообщений: 1

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

Входные данные
В первой строке содержится натуральное число N (1 <= N <= 100). Во второй строке записано N целых чисел A[i] (1 <= A[i] <= 100) - элементы последовательности.

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

Натолкните на мысль, пожалуйста. Спасибо
  #2  
Старый 03.03.2010, 03:01
гость

 
Сообщений: n/a

Сообщение от jura Посмотреть сообщение
Есть последовательность из N натуральных чисел. Требуется разбить ее на две группы так, чтобы модуль разности между суммой элементов в первой группе и суммой элементов во второй группе был минимальным

Входные данные
В первой строке содержится натуральное число N (1 <= N <= 100). Во второй строке записано N целых чисел A[i] (1 <= A[i] <= 100) - элементы последовательности.

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

Натолкните на мысль, пожалуйста. Спасибо
Ну динамика тут же, как вы и говорите.

Решайте подзадачи такого вида - можно ли разбить первые i чисел на две части, так чтобы сумма чисел в одной из них равнялась j.

0 <= i <= 100, 0 <= j <= 100*100, => 100^3 состояний, 2 перехода в каждом.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
динамическое программирование гость Задачи 8 12.03.2009 18:49
динамическое программирование. Артур Поиск и обсуждение книг/сайтов 9 19.01.2009 00:18
Помогите пож, динамическое программирование Hide Математические алгоритмы (другое) 3 26.12.2008 12:23
Задача на динамическое программирование Fedorenko Математические алгоритмы 4 30.06.2007 10:11
динамическое программирование по профилю artie Задачи 6 11.01.2007 18:01