3613. Olympic luggage

Being in London, Vasya bought for his family and friends a lot of all sorts of souvenirs and gifts. However, buying a ticket at the airport on the way back, he was very disappointed to know that the total weight of baggage should not exceed m grams.

Knowing the number of souvenirs and gifts bought by Vasya, help him to pack the luggage so that it will be as close as possible to the limit and, of course, did not exceed limit for the flight.

Input. The first line contains a weight restriction on luggage for the flight m (1 ≤ m ≤ 10000) and the number of items n (1 ≤ n ≤ 300) Vasya has.

The second line contains n numbers – the weight of each Vasya’s item. It is known that the weight of each object is not more than 100000 grams.

Output. Print one number – the maximum possible weight of Vasya’s luggage.

Sample input	Sample output
6 4 2 7 1 1	4

SOLUTION

dynamic programming - knapsack

Algorithm analysis

Declare an array mask, so that mask[i] will be set to 1, if it is possible to gain weight i with the available items. Initially set mask[0] = 1.

Let the array mask be already filled in the required way for some set of items. The next object of weight w arrives. Then we should set to 1 all such mask[i] (w ≤ i ≤ m) for which mask[i – w] = 1.

Example

Consider how the elements of the array mask are changed as the items are processed. The masses of items are given at the left.

The maximum weight of 4 is achieved for the subset {2, 1, 1}.

Algorithm realization

The array mask is stored as a bit mask, otherwise we get Memory Limit.

#define MAX 30000010

bitset<MAX> mask;

Read the input data. Set mask[0] = 1.

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

mask.set(0);

Consider the processing of the next object of weight w. Iteratte through the array from right to left and set to 1 all such mask[j] (w ≤ j ≤ m) for which 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);

}

Find the largest weight, not greater than m, that can be sent to baggage, and print it.

for(i = m;; i--)

if (mask[i] > 0) break;

printf("%d\n",i);