DP - Knapsack flipping the state formulation - Competitive Programming

DP - Knapsack flipping the state formulation

In this task we will see that the same problem can have several DP formulations that can be more suited for some situations.

Recall that we defined previously the DP subproblems as:

\(dp(i, c)\) is the maximum value we can obtain by selecting a subset of the objects \(0, 1 \ldots, i\) from a knapsack of capacity \(c\).

Note that we are basing ourselves on the bottom-up formulation.

This is not the only way the DP subproblems can be formulated. An alternative is to have the states depend on the value instead of the capacity. We define the states as pairs \((i, v)\) and the subproblems as:

\(dp(i, v)\) is the minimum knapsack capacity needed in order to achieve value \(v\) by selecting a subset of the objects \(0, 1 \ldots, i\).

If a value \(v\) is impossible to achieve, we define \(dp(i, v) = \infty\) for all \(i\).

To relate the subproblems and define the recurrence relation we need to think about what happens depending on whether we decide to skip or take the \(i\)-th item.

If we don't take item \(i\) then the minimum capacity needed to achieve value \(v\) with items \(0, \ldots, i\) is the same as for items \(0, \ldots, i - 1\). Thus, in this case, \(dp(i, v) = dp(i - 1, v)\).
If we take item \(i\) then we need capacity \(w_i\) plus the minimum capacity to achieve value \(v - v_i\) using items \(0, \ldots, i - 1\). Thus, in this case, \(dp(i, v) = w_i + dp(i - 1, v - v_i)\). Note that this option is undefined if \(v - v_i < 0\). To simplify the formulas, we will assume that, in this case, it evaluates to \(\infty\).

Therefore we can write that \(dp(i, v)\) is the minimum of those two options:

\begin{equation*} dp(i, v) = \min (dp(i - 1, v), w_i + dp(i - 1, v - v_i)) \end{equation*}

The base cases are when \(i = 0\). In this case the only achievable values are \(0\) with a knapsack of capacity \(0\) and \(v_0\) with a knapsack of capacity \(w_0\). Hence, \(dp()\)

\begin{equation*} dp(0, v) = \begin{cases} 0 & \quad \text{if } v = 0 \\ w_0 & \quad \text{if } v = v_0 \\ \infty & \quad \text{if } v \notin \{0, v_0\} \end{cases} \end{equation*}

How to you recover the answer in the end (the value, not the items themselves)? Think about it before reading futher.

The maximum value that can be achieved will correspond to the maximum \(v\) for which \(dp(n - 1, v)\) is smaller than or equal to the knapsack capacity.

With this formulation the number of states is \(O(n \cdot V)\) where \(V = v_0 + v_1 + \ldots + v_{n - 1}\). We can also write it as \(O(n^2 \cdot m_v)\) where \(m_v = \max_i v_i\) because \(V \leq n \cdot m_v\).

This can be useful for problems where the knapsack is very big because the time complexity does not depend on the knapsack capacity. It also shows that if all values are equal to \(1\) then the problem can be solved in polynomial time \(O(n^2)\). But if you think about it, this is obvious, and it is actually easy to solve it in this case in \(O(n \cdot \log(n))\).

Paste this command into your terminal:

The password to connect is

Knapsakc with small values

Write a solution for the Knapsack problem. You will need to apply memory compression to this formulation for your solution to be accepted. The process is analogous to the one for the other formulation.

Input

One line with two integers \(C\) and \(n\) giving the knapsack capacity and the number of items respectively.
\(n\) lines each with two integers \(w\) and \(v\) giving the weights and the values of each of the items.

Output

A single line with an integer giving the maximum value that can be achieved by taking a subset of the items with total weight at most \(C\).

Do not forget to print the answer as an int and not a double.

Constraints