Олімпійський багаж#3613

Олімпійський багаж (Розбір)

Об'явимо масив $ma s k$ , в якому $ma s k [i]$ прийме значення $1$ , якщо за допомогою наявних предметів можна набрати сумарну вагу $i$ . Спочатку покладемо $ma s k [0] = 1$ mask[0] = 1.

Припустимо, що масив $ma s k$ вже коректно заповнений для деякого набору предметів. Розглянемо наступний предмет ваги $w$ . Тоді необхідно встановити $ma s k [i] = 1$ mask[i] = 1 для всіх значень $i (w \leq i \leq m)$ i~(w \le i \le m), для яких виконується умова $ma s k [i - w] = 1$ mask[i - w] = 1.

Приклад

Розглянемо, як змінюються значення комірок масиву $ma s k$ під час обробки предметів. Ліворуч вказані ваги предметів.

Максимальна вага $4$ досягається для підмножини ${2, 1, 1}$ \{2, 1, 1\}.

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

Масив $ma s k$ зберігаємо у вигляді бітової маски, інакше рішення не вкладеться в обмеження по пам'яті.

#define MAX 30000010
bitset<MAX> mask;

Читаємо вхідні дані. Встановлюємо $ma s k [0] = 1$ mask[0] = 1.

scanf("%d %d",&m,&n);
mask.set(0);

Розглянемо обробку чергового предмета ваги $w$ . Проходимо по масиву справа наліво і встановлюємо $ma s k [j] = 1$ mask[j] = 1 для всіх значень $j (w \leq j \leq m)$ j~(w \le j \le m), для яких $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);
}

Після обробки всіх предметів знаходимо найбільшу вагу, що не перевищує $m$ , яку можна покласти в багаж, і виводимо її.

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