1661. Рюкзак Алладина

Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает – слишком большой вес рюкзак может просто не выдержать.

Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей.

Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак.

Будем считать, что в пещере имеются предметы n различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен s. Каждый предмет типа i имеет вес w_i и стоимость v_i (i = 1, 2, ..., n).

Вход. В первой строке содержится два натуральных числа s и n (1 ≤ s ≤ 250, 1 ≤ n ≤ 35) – максимальный вес предметов в рюкзаке и количество типов предметов. Следующие n строк содержат по два числа w_i  и v_i (1 ≤ w_i ≤ 250, 1 ≤ v_i ≤ 250) – вес предмета типа i и его стоимость.

Выход. Выведите максимальную стоимость груза, вес которого не превышает s.

Пример входа	Пример выхода
10 2 5 10 6 19	20

РЕШЕНИЕ

рюкзак

Анализ алгоритма

Пусть dp_k[s] – максимальная стоимость груза, вес которого не превышает s при условии, что будут использованы предметы первых k типов.

Если предмет k-го типа при составлении груза весом i:

· не использовать, то dp_k[i] = dp_k-1[i].

· использовать, то dp_k[i] = dp_k[i – w_k] + v_k.

Поскольку стоимость груза следует максимизировать, то

dp_k[i] = max(dp_k-1[i], dp_k[i – w_k] + v_k), w_k ≤ i ≤ s

Базовыми случаями являются:

dp₀[i] = 0 и dp_k[0] = 0

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

Объявим рабочие массивы:

· w[i] – вес предмета i-го типа;

· p[i] – стоимость предмета i-го типа;

· dp[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++)

{

Пересчитываем значения массива dp при условии использования предмета типа k. Количество предметов каждого типа не ограничено.

for (i = w[k]; i <= s; i++)

dp[i] = max(dp[i], dp[i - w[k]] + p[k]);

}

Выводим ответ.

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

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

#include <cstdio>

#include <algorithm>

#include <cstring>

#define MAXW 252

#define MAXN 37

#define INF 2000000000

using namespace std;

int w[MAXN], v[MAXN];

int dp[MAXN][MAXW];

int k, i, n, s;

int f(int k, int s)

{

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

if (s < 0) return -INF;

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

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

}

int main()

{

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

return 0;

}