Aladdin's knapsack#1661

Aladdin's knapsack (Editorial)

Let $d p_{k} [s]$ dp_k[s] be the maximum value of cargo with a weight of at most $s$ , considering only the first $k$ types of items.

Now, consider two possible options when forming cargo of weight $i$ :

Do not use an item of type $k$ : In this case, the optimal value remains unchanged, meaning:

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

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

Use an item of type $k$ : Then its weight $w_{k}$ w_k will occupy part of the knapsack's capacity, and the value will increase by $v_{k}$ v_k, meaning:

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

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

Since the goal is to maximize the cargo value, we obtain the following recurrence relation:

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

Base cases:

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

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

Let the function $f (k, s)$ f(k, s) compute the maximum value of cargo that can be packed into a knapsack with a weight limit of $s$ , using the first $k$ types of items. Then, the next recurrence relation holds:

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

Finally, we need to compute the value of $f (k, s)$ f(k, s) using memoization.

Algorithm implementation

Declare the arrays:

$w [i]$ — the weight of an item of type $i$ ;
$p [i]$ — the value of an item of type $i$ ;
$d p [i]$ — the maximum value of cargo with a weight of at most $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]);

Process $n$ types of items sequentially.

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

Update the values in the $d p$ array, considering the possibility of using items of type $k$ . Since the number of items of each type is unlimited, each item can be chosen multiple times.

  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 implementation — recursion

Declare the arrays:

$w [i]$ — the weight of an item of type $i$ ;
$p [i]$ — the value of an item of type $i$ ;
$d p [i]$ — the maximum value of cargo with a weight of at most $i$ ;

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

The function $f (k, s)$ f(k, s) computes the maximum value of cargo that can be packed into a knapsack with a weight limit of $s$ , using the first $k$ types of items.

int f(int k, int s)
{

If $k = 0$ k = 0 or $s = 0$ s = 0, the knapsack is empty, and its value is $0$ .

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

If $s < 0$ s < 0, we have exceeded the allowed weight, making this option invalid. Therefore, we return $- I N F$ (where $I N F$ is a sufficiently large number).

  if (s < 0) return -INF;

If the value of $f (k, s)$ f(k, s) is already computed, return it.

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

Compute $f (k, s)$ f(k, s) and store it in $d p [k] [s]$ dp[k][s].

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

The main part of the program. Read the input data.

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

Compute and print the answer.

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