Poçt göndərməsi#2509

Poçt göndərməsi (Həll təhlili)

Göndərilməli olan əşyalar alt çoxluğunu təsvir edən maska anlayışını daxil edək. Məsələn, $ma s k = 5 = 10 1_{2}$ mask = 5 = 101_2 maskası, sıfırıncı və ikinci əşyaları daxil edən alt çoxluğu təyin edir (əşyalar sıfırdan nömrələnir).

Hər bir alt çoxluq üçün onun ümumi çəkisini hesablayın, bu da göndərmə xərclərini təyin edir. Əgər bu çəki tam olaraq $1000$ gramm-a bərabərdirsə, $p \leq 1000$ p \le 1000 olduğu üçün, həmişə xüsusi təklifi istifadə etmək sərfəlidir.

Qoy $M in C os t [ma s k]$ MinCost[mask] maska ilə təyin olunan əşyalar alt çoxluğunun göndərilməsinin minimal (avro) xərclərini ifadə etsin. O zaman hər hansı $x$ maskası $ma s k$ alt çoxluğu olduğu halda belə münasibət yerinə yetirilir:

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

Maska $2^{n} - 1$ 2^n - 1, $n$ ədədli bütün alqoritmlə uyğun gəlir, beləliklə, məsələnin cavabı $M in C os t [2^{n} - 1]$ MinCost[2^n - 1] qiyməti olacaq.

Teorem. Bütün maskaların və onların alt maskalarının hesablanması $O (3^{n})$ O(3^n) vaxtında baş verir.

Sübut 1. $i$ -ci biti nəzərə alaq. Onun üçün üç variant mümkündür:

o, $ma s k$ dizisində və alt maska $s u b$ -da mövcuddur;
o, $ma s k$ dizisində mövcuddur, amma alt maska $s u b$ -da mövcud deyil;
o, $ma s k$ dizisində də, alt maska $s u b$ -da da yoxdur;

Bütövlükdə bitlərin sayı $n$ , deməli kombinasiyaların ümumi sayı $3^{n}$ 3^n-ə bərabərdir.

Sübut 2. Qoy $ma s k$ maskası $k$ quraşdırılmış bitlərə sahib olsun. Onda məhz $2^{k}$ 2^k alt maskalara sahib olacaq. Maskaların uzunluğunun $n$ , $k$ quraşdırılmış bitlərlə sayda $C_{n}^{k}$ C_n^k-yə bərabərliyini bərabərdir. Sonuç olaraq, kombinasiyaların ümumi sayı

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

Alqoritmin həyata keçirilməsi

Əşyaların kütlələri $m$ massivində saxlanacaq. $M in C os t [ma s k]$ MinCost[mask] hüceyrəsində $ma s k$ maskası ilə təyin olunan əşyalar alt çoxluğunun göndərilməsinin minimal xərcləri saxlanacaq.

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

Nəticə məlumatlarını oxuyuruq.

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

Dəyişəndə $ma s k$ , $0$ -dan $2^{n} - 1$ 2^n - 1-ə qədər bütün mümkün maskalara baxırıq.

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

Dəyişəndə $C os t$ -da $ma s k$ maskasına uyğun alt çoxluğun ümumi çəkisini qeyd edəcəyik. Bunun üçün $ma s k$ sayının ikilik təqdimatına baxaq: əgər $i$ mövqeyində $1$ varsa, onda $i$ -ci əşyanın çəkisini $C os t$ -a əlavə edəcəyik.

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

Əgər $C os t$ dəyəri tam olaraq $1000$ -ə bərabərdirsə, onda $p \leq 1000$ p \le 1000 olduğu üçün, $C os t$ dəyişəninə $p$ dəyərini təyin edirik.

  if (Cost == 1000) Cost = p;

Hesablanan göndərmə qiymətini $M in C os t$ massivinin müvafiq hücrəsinə daxil edək.

  MinCost[mask] = Cost;
}

Hər bir $ma s k$ maskası üçün $x \subset ma s k$ x \sub mask olan bütün alt çoxluqları təyin edirik (mask $x$ $ma s k$ alt çoxluğu yalnız o halda olur ki, $ma s k A N D x$ mask~AND~x $x$ -ə bərabər olur). Əgər $ma s k$ maskasına uyğun alt çoxluqdan $x$ maskasına uyğun alt çoxluğu çıxsaq, $ma s k X O R x$ mask~XOR~x maskalı çoxluq alınır.

Məsələn, əgər $ma s k = 110 1_{2}$ mask = 1101_2, $x = 100 1_{2}$ x = 1001_2, onda $ma s k X O R x = 10 0_{2}$ mask~XOR~x = 100_2, bu, çoxluğun nəzəri əməliyyatına uyğun gəlir ${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++)

Tapşırığın təhlilində göstərilən rekursiv əlaqəyə görə $M in C os t [ma s k]$ MinCost[mask] dəyərini yenidən hesablayırıq.

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

Cavabı çıxarırıq, bu da $M in C os t [2^{n} - 1]$ MinCost[2^n - 1] hücrəsində yerləşir.

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

O(3^n) qiymətləndirməsi ilə həyata keçirilməsi

Konstant və massivlərin elan edilməsi.

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

Mask $ma s k$ üçün bütün alt maskalarını $s u b$ -u baxmaq və

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)

mümkün olan minimum dəyərləri tapmaq lazımdır.

Bu əlavə simmetriya nəzərə alındıqda, yalnız $s u b \geq ma s k X O R s u b$ sub \ge mask~XOR~sub şərtinin yerinə yetirildiyi alt maskaları nəzərə almaq kifayətdir.

unsigned int FindCost(int mask)
{
  if (MinCost[mask] != MAX) return MinCost[mask];
  // sub maska maskasının bütün alt maskalarını nəzərdən keçirir
  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++

Proqramın əsas hissəsi. Hələ göndərmə xərcləri məlum olmayan uyğun alt çoxluqlar üçün $M in C os t [ma s k] = - 1$ MinCost[mask] = -1 təyin edirik.

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

Nəticə məlumatlarını oxuyuruq.

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

Əgər müəyyən alt çoxluğun xərcləri $1000$ -dən çox deyilsə (daha az deyil, çünki $p = 1000$ p = 1000 ola bilər), onda xüsusi təklifi onlardan istifadə etmək olmaz. Belə alt çoxluqlar üçün dərhal $M in C os t [ma s k]$ MinCost[mask] əşyaların xərcləri cəmi kimi hesablanır. Əgər əşyaların xərcləri tam olaraq $1000$ -ə bərabərdirsə, $M in C os t [ma s k] = p$ MinCost[mask] = p təyin edirik.

Buna görə, balaca alt çoxluqlara aid məlum olan minimal xərcləri əvvəlcədən doldururuq. Bu, proqramın işini daha səmərəli edir.

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

Cavabı çıxarırıq. Bütün əşyalar cəmi $2^{n} - 1$ 2^n - 1 maskası ilə təyin olunur, onun ikilik təqdimatı $n$ ədədindən ibarətdir.

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