3613. Olympic luggage

 

While staying in London, Vasya bought a large number of various souvenirs and gifts for himself, his relatives, and his friends. However, when purchasing a return flight ticket at the airport, he learned with great disappointment that the total weight of his luggage must not exceed m grams.

Given the number of souvenirs and gifts purchased by Vasya, help him pack his luggage so that its total weight is as close as possible to the specified limit and, of course, does not exceed the allowed restriction for the flight.

 

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

The second line contains n numbers – the weights of Vasya's items. It is known that the weight of each item does not exceed 105 grams.

 

Output. Print the maximum possible total weight of Vasya’s luggage that does not exceed the given limit.

 

Sample input

Sample output

6 4

2 7 1 1

4

 

 

SOLUTION

dynamic programming - knapsack

 

Algorithm analysis

Define an array mask, where mask[i] is set to 1 if it is possible to obtain a total weight of i using the available items. Initially, we set mask[0] = 1.

Assume that the array mask has already been correctly filled for some set of items. Consider the next item with weight w. Then we need to set mask[i] = 1 for all values i (w ≤ i ≤ m) such that the condition mask[i – w] = 1 holds.

 

Example

Let us examine how the values of the cells in the mask array change as the items are processed. The item weights are shown on the left.

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

 

Algorithm implementation

We store the mask array as a bitmask; otherwise, the solution will not fit within the 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 processing the next item with weight w. Traverse the array from right to left and set mask[j] = 1 for all values j (w ≤ j ≤ m) such that 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);

}

 

After all items have been processed, find the largest weight not exceeding m that can be packed into the luggage and print it.

 

for (i = m;; i--)

  if (mask[i] > 0) break;

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