Olympic luggage#3613

Olympic luggage (Editorial)

Define an array $ma s k$ , where $ma s k [i]$ is set to $1$ if it is possible to obtain a total weight of $i$ using the available items. Initially, we set $ma s k [0] = 1$ 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 $ma s k [i] = 1$ mask[i] = 1 for all values $i (w \leq i \leq m)$ i~(w \le i \le m) such that the condition $ma s k [i - w] = 1$ mask[i - w] = 1 holds.

Example

Let us examine how the values of the cells in the $ma s k$ 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}$ \{2, 1, 1\}.

Algorithm implementation

We store the $ma s k$ 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 $ma s k [0] = 1$ 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 $ma s k [j] = 1$ mask[j] = 1 for all values $j (w \leq j \leq m)$ j~(w \le j \le m) such that $ma s k [j - w] = 1$ 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);