Knapsack 1

Knapsack 1

Atcoder medium

Given a set of \(N\) elements, each element \(i\) has a weight \(w_i\) and value \(v_i\). Select a subset of elements such that the total weight does not exceed \(W\). Determine the maximum possible total value.

Solution

We will solve this problem using dynamic programming.

Let’s define the state:

\(f(i, capacity)\) is the maximum total value possible considering only elements up to i with maximum possible weight capacity.

Next, we define the transition. At each step, we can either include element \(i\) or skip it.

In case we include element \(i\), the transition will be:

\(f(i, capacity) = f(i - 1, capacity - w_i) + v_i\)

In case we skip it, the transition will be:

\(f(i, capacity) = f(i - 1, capacity)\)

Since we cannot determine which option is better in advance, we take the maximum of the two possible transitions.

\(f(i, capacity) = max(f(i - 1, capacity ), f(i - 1, capacity - w_i) + v_i)\)

In this problem our base case will be:

\(f(0,\text{capacity}) = \begin{cases} v_i, & \text{if capacity} \ge w_i,\\[6pt] 0, & \text{if capacity} < w_i. \end{cases}\)

The space complexity of the algorithm is determined by the number of states, which is \(O(N \cdot W)\).

The time complexity is the number of states \(N \cdot W\) multiplied by the complexity of each transition \(O(1)\), so the overall time complexity is \(O(N \cdot W)\) as well.

#include <iostream>
using namespace std;

long long dp[200][200000];
int v[200], w[200]; 


long long f (int i, int capacity) {

    if (i == 0) {
    if (capacity < w[i]) {
      return 0;
    }
    else {
      return v[i];
    }
    }

  if (dp[i][capacity] != -1) {
    return dp[i][capacity];
  }

  // case of not taking item i
  dp[i][capacity] = f(i - 1, capacity);

  // case of taking item i
  if (capacity >= w[i]) {
    dp[i][capacity] = max(dp[i][capacity], f(i - 1, capacity - w[i]) + v[i]);
  }

  return dp[i][capacity];
}


int main() {
  
    for (int i = 0; i < 200; i++) {
    for (int j = 0; j < 200000; j++) {
          dp[i][j] = -1;
    }
    }

    int n, weight;
    cin >> n >> weight;
  
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> v[i];
  }

  cout << f(n - 1, weight) << endl;
}