The post office#2509

The post office (Editorial)

Let's introduce the notion of a mask that represents a subset of items to be shipped. For example, the mask $ma s k = 5 = 10 1_{2}$ mask = 5 = 101_2 specifies the subset containing the $0$ -th and $2$ -nd items (items are numbered from zero).

For each subset, we compute its total weight, which determines the shipping cost. If this weight is exactly $1000$ grams, then since $p \leq 1000$ p \le 1000, it is always beneficial to use the special offer.

Let $M in C os t [ma s k]$ MinCost[mask] denote the minimum cost (in euros) of shipping the subset of items represented by $ma s k$ . Then for any mask $x$ that is a subset of $ma s k$ , the following relation holds:

M in C os t [ma s k] = x \subset ma s k min (M in C os t [ma s k x or x] + M in C os t [x])

MinCost[mask] = \min_{x \sub mask} (MinCost[mask~xor~x] + MinCost[x])

Since the mask $2^{n} - 1$ 2^n - 1 corresponds to the entire set of $n$ items, the answer to the problem will be the value $M in C os t [2^{n} - 1]$ MinCost[2^n - 1].

Theorem. Enumerating all masks and all of their submasks takes $O (3^{n})$ O(3^n) time.

Proof 1. Consider the $i$ -th bit. There are three possible cases for it:

it is included in the mask $ma s k$ and included in the submask $s u b$ ;
it is included in the mask $ma s k$ but not included in the submask $s u b$ ;
it is included in neither the mask $ma s k$ nor the submask $s u b$ ;

There are $n$ bits in total, so the total number of different combinations is $3^{n}$ 3^n.

Proof 2. Let a mask $ma s k$ contain $k$ set bits. Then it has exactly $2^{k}$ 2^k submasks. The number of masks of length $n$ with exactly $k$ set bits is $C_{n}^{k}$ C_n^k. Therefore, the total number of combinations is

k = 0 \sum n C_{n}^{k} 2^{k} = (1 + 2)^{n} = 3^{n}

\sum_{k=0}^n C_n^k 2^k = (1 + 2)^n = 3^n

Algorithm implementation

We'll store the item weights in the array $m$ . In the cell $M in C os t [ma s k]$ MinCost[mask], we'll store the minimum shipping cost for the subset of items represented by the mask $ma s k$ .

int m[15], MinCost[1 << 14];

Read the input data.

scanf("%d %d",&n,&p);
for (i = 0; i < n; i++) scanf("%d",&m[i]);

In the variable $ma s k$ , iterate over all possible masks from $0$ to $2^{n} - 1$ 2^n - 1.

for (mask = 0; mask < (1 << n); mask++)
{

Store in the variable $C os t$ the total weight of the subset of items corresponding to the mask $ma s k$ . To do this, examine the binary representation of $ma s k$ : if the bit at position $i$ is $1$ , then add the weight of the $i$ -th item to $C os t$ .

  for (Cost = i = 0; i < n; i++)
    if (mask & (1 << i)) Cost += m[i];

If the value of $C os t$ is strictly equal to $1000$ , then since the problem states that $p \leq 1000$ p \le 1000, assign the value $p$ to $C os t$ .

  if (Cost == 1000) Cost = p;

Store the computed shipping cost in the corresponding cell of the $M in C os t$ array.

  MinCost[mask] = Cost;
}

For each mask $ma s k$ , iterate over all subsets $x \subset ma s k$ x \sub mask (the mask $x$ is a subset of $ma s k$ if and only if $ma s k A N D x$ mask~AND~x equals $x$ ). If we subtract the set corresponding to $x$ from the set corresponding to $ma s k$ , we get the set with mask $ma s k X O R x$ mask~XOR~x.

For example, if $ma s k = 110 1_{2}$ mask = 1101_2 and $x = 100 1_{2}$ x = 1001_2, then $ma s k X O R x = 10 0_{2}$ mask~XOR~x = 100_2, which corresponds to the set-theoretic operation ${1, 3, 4} ∖ {1, 4} = {3}$ \{1, 3, 4\} \setminus \{1, 4\} = \{3\}.

for (mask = 0; mask < (1 << n); mask++)
  for (x = 0; x < mask; x++)

Recompute the value of $M in C os t [ma s k]$ MinCost[mask] according to the recurrence relation given in the problem analysis.

    if ((mask & x) == x) 
      MinCost[mask] = min(MinCost[mask],MinCost[mask^x] + MinCost[x]);

Print the answer, which is stored in the cell $M in C os t [2^{n} - 1]$ MinCost[2^n - 1].

printf("%d\n",MinCost[(1 << n) - 1]);

Algorithm implementation with complexity O(3^n)

Declare the constant and the arrays.

#define MAX 0xFFFFFFFF
unsigned int m[15], MinCost[1 << 14];

For a mask $ma s k$ , it is necessary to iterate over all its submasks $s u b$ and find the minimum among all possible values

F in d C os t (s u b) + F in d C os t (ma s k X O R s u b)

FindCost(sub) + FindCost(mask~XOR~sub)

Due to the symmetry of this sum, it is sufficient to consider only those submasks $s u b$ for which the condition $s u b \geq ma s k X O R s u b$ sub \ge mask~XOR~sub holds.

unsigned int FindCost(int mask)
{
  if (MinCost[mask] != MAX) return MinCost[mask];
  // sub перебирает все подмаски маски mask
  for (int sub = (mask - 1) & mask; 
           sub >= mask ^ sub; sub = (sub - 1) & mask)
    MinCost[mask] = 
            min(MinCost[mask], FindCost(sub) + FindCost(mask ^ sub));
  return MinCost[mask];
}

C++

The main part of the program. Set $M in C os t [ma s k] = - 1$ MinCost[mask] = -1 for all masks whose shipping cost for the corresponding set of items has not yet been computed.

memset(MinCost,0xFF,sizeof(MinCost));

Read the input data.

scanf("%d %d",&n,&p);
for(i = 0; i < n; i++) scanf("%d",&m[i]);

If the cost of a certain subset of items does not exceed $1000$ (specifically, not more, not less, since the case $p = 1000$ p = 1000 is possible), then the special offer cannot be applied to their shipment. For such subsets, $M in C os t [ma s k]$ MinCost[mask] can be immediately computed as the sum of the costs of all items. If the sum of item costs is exactly $1000$ , then we assign $M in C os t [ma s k] = p$ MinCost[mask] = p.

Thus, we preliminarily fill in the known minimum costs for small subsets. This increases the efficiency of the program.

for (mask = 0; mask < (1 << n); mask++)
{
  for(Cost = i = 0; i < n; i++)
    if (mask & (1 << i)) Cost += m[i];
  if (Cost == 1000) Cost = p;
  if (Cost <= 1000) MinCost[mask] = Cost;
}

C++

Print the answer. The entire set of items is represented by the mask $2^{n} - 1$ 2^n - 1, whose binary representation consists of $n$ ones.

printf("%u\n",FindCost((1 << n) - 1));