3613. Олимпийский багаж
Находясь в
Лондоне, Вася накупил себе, родственникам и друзьям множество всевозможных
сувениров и подарков. Однако при покупке билета на обратный рейс в аэропорту он
с большим разочарованием узнал, что общий вес его багажа не должен превышать m грамм.
Зная количество
приобретённых Васей сувениров и подарков, помогите ему упаковать багаж так,
чтобы его общий вес был как можно ближе к установленному пределу и, разумеется,
не превышал допустимого ограничения для авиарейса.
Вход. В первой строке задано ограничение на вес багажа для
авиарейса m (1 ≤ m
≤ 10000) и количество предметов у Васи n (1 ≤ n ≤
300).
Во второй строке записано n чисел – веса каждого из Васиных предметов. Известно, что
вес каждого предмета не превышает 105 грамм.
Выход. Выведите максимально возможный общий вес Васиного багажа, не
превышающий установленного ограничения.
|
Пример
входа |
Пример
выхода |
|
6 4 2 7 1 1 |
4 |
РЕШЕНИЕ
динамическое программирование - рюкзак
Анализ алгоритма
Объявим массив mask,
в котором mask[i] примет значение 1, если с помощью имеющихся
предметов можно набрать суммарный вес i. Изначально
положим mask[0] = 1.
Предположим, что массив mask уже корректно заполнен для
некоторого набора предметов. Рассмотрим следующий предмет веса w. Тогда необходимо установить mask[i] = 1 для всех значений i (w ≤ i ≤ m), для которых выполняется условие mask[i – w] = 1.
Рассмотрим, как изменяются значения ячеек массива mask
по мере обработки предметов. Слева указаны веса предметов.
Максимальный вес 4 достигается для подмножества {2, 1, 1}.
Реализация
алгоритма
Массив mask
храним в виде битовой маски, иначе решение не уложится в ограничение по памяти.
#define MAX 30000010
bitset<MAX> mask;
Читаем входные данные. Устанавливаем
mask[0] = 1.
scanf("%d %d",&m,&n);
mask.set(0);
Рассмотрим обработку
очередного предмета веса w. Проходим по
массиву справа налево и устанавливаем mask[j] = 1 для всех значений j (w ≤ j ≤ m), для которых mask[j – w] = 1.
for (i = 0; i < n; i++)
{
scanf("%d",&w);
for (j = m; j >= w; j--)
if (mask[j - w] == 1) mask.set(j);
}
После обработки всех предметов
находим наибольший вес, не превышающий m, который можно положить в
багаж, и выводим его.
for (i = m;; i--)
if (mask[i] > 0) break;
printf("%d\n",i);