3613. Олимпийский багаж

Пребывая в Лондоне, Вася накупил себе, родным и друзьям множество всевозможных сувениров и подарков. Однако, покупая в аэропорту билет на обратную дорогу, он с большим разочарованием узнал, что общий вес его багажа не должен превышать m грамм.

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

Вход. В первой строке задано ограничение на багаж для авиарейса m (1 ≤ m ≤ 10000) и количество предметов у Васи n (1 ≤ n ≤ 300).

Во второй строке находится n чисел – соответственно вес каждого из предметов Васи. Известно, что вес каждого предмета не превышает 100000 грамм.

Выход. Выведите единственное число – максимально допустимый вес Васиного багажа.

Пример входа	Пример выхода
6 4 2 7 1 1	4

РЕШЕНИЕ

динамическое программирование - рюкзак

Анализ алгоритма

Заведем массив mask, в котором mask[i] установим в 1, если можно набрать вес i имеющимися предметами. Изначально положим mask[0] = 1.

Пусть массив mask уже заполнен требуемым образом для некоторого множества предметов. Приходит следующий предмет веса w. Тогда следует положить равным 1 все такие mask[i] (w ≤ i ≤ m), для которых mask[i – w] = 1.

Пример

Рассмотрим как изменяются ячейки массива mask по мере обработки предметов. Слева указаны массы предметов.

Максимальный вес 4 достигается для подмножества {2, 1, 1}.

Реализация алгоритма

Массив mask храним в виде битовой маски, иначе получим Memory Limit.

#define MAX 30000010

bitset<MAX> mask;

Читаем входные данные. Устанавливаем mask[0] = 1.

scanf("%d %d",&m,&n);

mask.set(0);

Рассмотрим обработку очередного предмета весом w. Проходим по массиву справа налево и устанавливаем в 1 все такие mask[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);