Поштове відправлення#2509

Поштове відправлення (Розбір)

Введемо поняття маски, що описує підмножину предметів, які пересилаються. Наприклад, маска $ma s k = 5 = 10 1_{2}$ mask = 5 = 101_2 визначає підмножину, що включає нульовий і другий предмети (предмети нумеруються з нуля).

Для кожної підмножини обчислимо його сумарну вагу, яка визначає вартість пересилання. Якщо ця вага дорівнює рівно $1000$ грамів, то, оскільки $p \leq 1000$ p \le 1000, завжди вигідно скористатися спеціальною пропозицією.

Нехай $M in C os t [ma s k]$ MinCost[mask] позначає мінімальну вартість (в євро) пересилання підмножини предметів, заданої маскою $ma s k$ . Тоді для будь-якої маски $x$ , яка є підмножиною $ma s k$ , виконується таке співвідношення:

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])

Оскільки маска $2^{n} - 1$ 2^n - 1 відповідає всій множині з $n$ предметів, відповіддю на задачу буде значення $M in C os t [2^{n} - 1]$ MinCost[2^n - 1].

Теорема. Перебір усіх масок і всіх їх підмасок виконується за $O (3^{n})$ O(3^n).

Доведення 1. Розглянемо $i$ -тий біт. Для нього можливі три варіанти:

він входить в маску $ma s k$ і входить в підмаску $s u b$ ;
він входить в маску $ma s k$ , але не входить в підмаску $s u b$ ;
він не входить ні в маску $ma s k$ , ні в підмаску $s u b$ ;

Загалом $n$ бітів, отже загальна кількість різних комбінацій дорівнює $3^{n}$ 3^n.

Доведення 2. Нехай маска $ma s k$ містить $k$ встановлених бітів. Тоді вона має рівно $2^{k}$ 2^k підмасок. Кількість масок довжини $n$ з рівно $k$ встановленими бітами дорівнює $C_{n}^{k}$ C_n^k. Отже, загальна кількість комбінацій дорівнює

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

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

Маси предметів зберігатимемо в масиві $m$ . У ячейці $M in C os t [ma s k]$ MinCost[mask] зберігатимемо мінімальну вартість пересилання підмножини предметів, заданої маскою $ma s k$ .

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

Читаємо вхідні дані.

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

У змінній $ma s k$ перебираємо всі можливі маски від $0$ до $2^{n} - 1$ 2^n - 1.

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

У змінну $C os t$ занесемо сумарну вагу підмножини предметів, що відповідає масці $ma s k$ . Для цього переглянемо двійкове представлення числа $ma s k$ : якщо на позиції $i$ стоїть $1$ , то додамо до $C os t$ вагу $i$ -го предмету.

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

Якщо значення $C os t$ строго дорівнює $1000$ , то, оскільки за умовою $p \leq 1000$ p \le 1000, присвоюємо змінній $C os t$ значення $p$ .

  if (Cost == 1000) Cost = p;

Записуємо обчислену вартість пересилання у відповідну ячейку масиву $M in C os t$ .

  MinCost[mask] = Cost;
}

Для кожної маски $ma s k$ перебираємо всі підмножини $x \subset ma s k$ x \sub mask (маска $x$ є підмножиною $ma s k$ тоді і тільки тоді, коли $ma s k A N D x$ mask~AND~x дорівнює $x$ ). Якщо з множини, що відповідає масці $ma s k$ , вичитати множину, що відповідає $x$ , то вийде множина з маскою $ma s k X O R x$ mask~XOR~x.

Наприклад, якщо $ma s k = 110 1_{2}$ mask = 1101_2, $x = 100 1_{2}$ x = 1001_2, то $ma s k X O R x = 10 0_{2}$ mask~XOR~x = 100_2, що відповідає теоретико-множинній операції ${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++)

Перераховуємо значення $M in C os t [ma s k]$ MinCost[mask] згідно з рекурентним співвідношенням, наведеним в аналізі задачі.

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

Виводимо відповідь, яка знаходиться в ячейці $M in C os t [2^{n} - 1]$ MinCost[2^n - 1].

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

Реалізація з оцінкою O(3^n)

Оголосимо константу та масиви.

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

Для маски $ma s k$ необхідно перебрати всі її підмаски $s u b$ і знайти мінімум серед усіх можливих значень

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)

Через симетрію цієї суми досить розглядати тільки ті підмаски $s u b$ , для яких виконується умова $s u b \geq ma s k X O R s u b$ sub \ge mask~XOR~sub.

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++

Основна частина програми. Установимо $M in C os t [ma s k] = - 1$ MinCost[mask] = -1 для всіх масок, вартість відправки відповідного набору предметів для яких ще не була обчислена.

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

Читаємо вхідні дані.

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

Якщо вартість деякої підмножини предметів не перевищує $1000$ (саме не більше, а не менше, так як можливий випадок $p = 1000$ p = 1000), то спеціальна пропозиція для їх відправки застосувати не можна. Для таких підмножин можна відразу обчислити $M in C os t [ma s k]$ MinCost[mask] як суму вартостей всіх предметів. Якщо сума вартостей предметів дорівнює рівно $1000$ , то присвоюємо $M in C os t [ma s k] = p$ MinCost[mask] = p.

Таким чином ми попередньо заповнюємо відомі мінімальні вартості для малих підмножин. Це збільшує ефективність роботи програми.

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++

Виводимо відповідь. Усі множини предметів задаються маскою $2^{n} - 1$ 2^n - 1, двійкове представлення якої складається з $n$ одиниць.

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