Olimpiya baqajı (Həll təhlili)

$mask$ adlanan bir massiv təsvir edək, burada $mask[i]$ dəyəri 1 olacaq, əgər mövcud əşyalar ilə ümumi çəkisi $i$ olan yüki əldə etmək mümkündürsə. İbtidai şərt olaraq, mask[0] = 1 təyin edək.

Tutaq ki, $mask$ massivi artıq müəyyən əşyalar dəsti üçün düzgün doldurulmuşdur. $w$ çəkili növbəti əşyanı nəzərdən keçirək. O zaman, mask[i - w] = 1 şərtinin ödəndiyi bütün i~(w \le i \le m) dəyərləri üçün mask[i] = 1 təyin etmək lazımdır.

Nümunə

Əşyaların işlənməsi zamanı $mask$ massivinin hüceyrə dəyərlərinin necə dəyişəcəyini nəzərdən keçirək. Sol tərəfdə əşyaların çəkiləri göstərilir.

Maksimum çəki $4$, alt cəm \{2, 1, 1\} olan dəstə üçün əldə edilir.

Alqoritmin həyata keçirilməsi

$mask$ massivini bit maskası kimi saxlayırıq, başqa cür həll yaddaş məhdudiyyəti daxilində olmaz.

#define MAX 30000010
bitset\u003cMAX\u003e mask;

Giriş məlumatlarını oxuyuruq. mask[0] = 1 təyin edirik.

scanf("%d %d",\u0026m,\u0026n);
mask.set(0);

Növbəti $w$ çəkili əşyanın emalını nəzərdən keçirək. Məssivi sağdan sola keçir və mask[j - w] = 1 olan bütün j~(w \le j \le m) dəyərləri üçün mask[j] = 1 təyin edirik.

for (i = 0; i \u003c n; i++)
{
  scanf("%d",\u0026w);
  for (j = m; j \u003e\u003d w; j--)
   if (mask[j - w] == 1) mask.set(j);
}

Bütün əşyaların emalından sonra m-ə bərabər və ya m-dən böyük olmayan ən böyük çəki tapılır və çıxışa verilir.

for (i = m;; i--)
  if (mask[i] \u003e 0) break;
printf("%d\n",i);