Рюкзак Аладдіна#1661

Рюкзак Аладдіна (Розбір)

Нехай $d p_{k} [s]$ dp_k[s] — максимальна вартість вантажу вагою не більше $s$ , якщо дозволено використовувати лише предмети перших $k$ типів.

Розглянемо два можливих варіанти при складанні вантажу вагою $i$ :

Не використовувати предмет $k$ -го типу: в цьому випадку оптимальне значення не зміниться, тобто

d p_{k} [i] = d p_{k - 1} [i]

dp_k[i] = dp_{k - 1}[i]

Використовувати предмет $k$ -го типу: тоді його вага $w_{k}$ w_k займе частину місткості рюкзака, а вартість збільшиться на $v_{k}$ v_k, тобто

d p_{k} [i] = d p_{k} [i - w_{k}] + v_{k} .

dp_k[i] = dp_k[i - w_k] + v_k.

Оскільки потрібно максимізувати вартість вантажу, отримуємо рекурентне співвідношення:

d p_{k} [i] = ma x (d p_{k - 1} [i], d p_{k} [i - w_{k}] + v_{k}), w_{k} \leq i \leq s

dp_k[i] = max(dp_{k - 1}[i], dp_k[i - w_k] + v_k), w_k \le i \le s

Базові випадки:

d p_{0} [i] = 0 і d p_{k} [0] = 0

dp_0[i] = 0~і~dp_k[0] = 0

Нехай функція $f (k, s)$ f(k, s) обчислює максимальну вартість вантажу, який можна зібрати в рюкзак вагою не більше $s$ , використовуючи перші $k$ типів предметів. Тоді має місце рекурентне співвідношення:

f (k, s) = ma x (f (k - 1, s), f (k, s - w [k]) + v [k])

f(k, s) = max(f(k - 1, s), f(k, s - w[k]) + v[k])

Залишилося обчислити значення функції $f (k, s)$ f(k, s) використовуючи мемоізацію.

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

Оголосимо робочі масиви:

$w [i]$ — вага предмета $i$ -го типу;
$p [i]$ — вартість предмета $i$ -го типу;
$d p [i]$ — максимальна вартість вантажу вагою не більше $i$ ;

#define MAXW 252
#define MAXN 37
int w[MAXN], p[MAXN];
int dp[MAXW];

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

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

Послідовно обробляємо $n$ типів предметів.

for (k = 0; k < n; k++)
{

Перераховуємо значення масиву $d p$ , враховуючи можливість використання предметів типу $k$ . Оскільки кількість предметів кожного типу не обмежена, кожен предмет можна вибирати декілька разів.

  for (i = w[k]; i <= s; i++)
    dp[i] = max(dp[i], dp[i - w[k]] + p[k]);
}

Виводимо відповідь.

printf("%d\n", dp[s]);

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

Оголосимо робочі масиви:

$w [i]$ — вага предмета $i$ -го типу;
$p [i]$ — вартість предмета $i$ -го типу;
$d p [i]$ — максимальна вартість вантажу вагою не більше $i$ ;

#define MAXW 252
#define MAXN 37
#define INF 2000000000
int w[MAXN], v[MAXN];
int dp[MAXN][MAXW];

Функція $f (k, s)$ f(k, s) обчислює максимальну вартість вантажу, який можна зібрати в рюкзак вагою не більше $s$ , використовуючи перші $k$ типів предметів.

int f(int k, int s)
{

Якщо $k = 0$ k = 0 або $s = 0$ s = 0, то рюкзак порожній, і його вартість дорівнює $0$ .

  if (k == 0 || s == 0) return 0;

Якщо $s < 0$ s < 0, то ми перевищили допустиму вагу, і цей варіант не має сенсу. Тому повертаємо $- I N F$ ( $I N F$ — це деяке велике число).

  if (s < 0) return -INF;

Якщо значення $f (k, s)$ f(k, s) вже обчислено, то повертаємо його.

  if (dp[k][s] != -1) return dp[k][s];

Обчислюємо значення $f (k, s)$ f(k, s) і запам'ятовуємо його в $d p [k] [s]$ dp[k][s].

  return dp[k][s] = max(f(k - 1, s), f(k, s - w[k]) + v[k]);
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &s, &n);
for (i = 1; i <= n; i++)
  scanf("%d %d", &w[i], &v[i]);

Обчислюємо і виводимо відповідь.

memset(dp, -1, sizeof(dp));
printf("%d\n", f(n, s));