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:
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()\)
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))\).