1661. Aladdin’s knapsack

Entering the cave with treasures, our Aladdin did not take an old blackened lamp. He rushed to collect the gold coins and precious stones into his knapsack. He would, of course, take everything, but miracles do not happen – too much weight the knapsack cannot hold.

Many times he laid out one thing and put others in their place, trying to raise the value of the jewels as high as possible.

Determine the maximum value of weight that Aladdin can put in his knapsack.

We will assume that in the cave there are objects of n different types, the number of objects of each type is not limited. The maximum weight that a knapsack can hold is s. Each item of type i has the weight w_i and cost v_i (i = 1, 2, ..., n).

Input. The first line contains two integers s and n (1 ≤ s ≤ 250, 1 ≤ n ≤ 35) – the maximum possible weight of items in the knapsack and the number of types of items. Each of the next n  lines contains two numbers w_i and v_i (1 ≤ w_i ≤ 250, 1 ≤ v_i ≤ 250) – the weight of item of type i and its cost.

Output. Print the maximum value of the loading, which weight does not exceed s.

Sample input	Sample output
10 2 5 10 6 19	20

SOLUTION

knapsack

Algorithm analysis

Let dp_k[s] be the maximum cost of treasures which weight does not exceed s, provided that items of the first k types are used.

If an item of type k when composing a load of weight i:

· not to use, then dp_k[i] = dp_k-1[i].

· to use, then dp_k[i] = dp_k[i – w_k] + v_k.

Since the cost of the loading should be maximized, then

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

The base cases are:

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

Algorithm realization

Declare the arrays:

· w[i] – the weight of the item of type i;

· p[i] – the cost of the item of type i;

· dp[i] – the maximum cost of load which weight does not exceed i;

#define MAXW 252

#define MAXN 37

int w[MAXN], p[MAXN];

int dp[MAXW];

Read the input data.

scanf("%d %d", &s, &n);

for (i = 0; i < n; i++)

scanf("%d %d", &w[i], &p[i]);

Sequentially process n types of items.

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

{

Recompute the values of the dp array, provided that an item of type k is used. The number of items of each type is not limited.

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

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

}

Print the answer.

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

Algorithm realization – recursion

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

}