Помощь - Поиск - Пользователи - Календарь
Полная версия: поис оптимального варианта
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
compiler
Добрый день!
Сегодня был на районной олимпиаде и встретил) такую задачу

В кондитирском магазине лежит ряд пакетов с пакетами. Для каждого пакета известно количество конфет в нем . Покупатель может взять в одну руку два соседних пакета и в другую - тоже два соседних покета(возможно, в другом конце ряда). При этом он хочет, чтобы количество конфет в четырех взятых им пакетах было максимальным. Напишите программу Sweet, которая решает за покупателя эту задачу.
4<=количество пакетов<=80
входные данные
кол. пакетов, кол. конфет в каждом пакете
выходные данные
намера пакетов(попарно)

вотс..
чесно говоря варианты есть, но хотелось бы узнать оптимальный алгоритм.

заранее благодарен.
andriano
Я бы действовал так:
За первый проход нашел максимальную пару из двух подряд идущих пакетов.
Исключил найденную пару.
За второй проход нашел вторую пару среди осавшихся.
Если вторая пара будет лежать по обе стороны от первой, то перекомпоновать пары.

Сложность O(n).
compiler
пожалуй да... это было бы хорошее решение...

спасибо!

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.