One of the fundamental optimization problems in computer science is the knapsack problem, which requires selecting a group of items based on their individual values and weights in order to obtain the maximum possible value while keeping the overall weight of the selection under a specified limit.
The problem is to distribute $n$ items, each with size $s_i$ and value $v_i$ into a knapsack of capacity $C$. The goal is to maximise the value of items in the knapsack, contained by $\sum s_i < C$.
A key restriction of the dynamic programming approach is that the sizes of items, $s_i$ must be integers.
The naive approach is a brute force approach that has exponential complexity.
One approach we could use is a greedy approach where we pick the elements with the maximum ratio of value of weight.
However, this can be easily disproved as yielding an incorrect solution.
The other approach is a DP approach which attempts to write the recurrence for the solution as follows. First, define the solution to the problem with the first $n-1$ items and capacity $C$ as solution(items[], n, C). Then the solution becomes:
if items[n - 1] < C:
solution(items[], n, C) = max(
solution(items[], n - 1, C),
solution(items[], n - 1, C - items[n-1].weight) + items[n-1].value
)
Now, the number of sub-problems is $O(nC)$ because this is the number of possible parameters we can have for our function. Computing each sub-problem takes $O(1)$ time so if we directly convert this into a DP problem, we are going to end up with a $O(nC)$ runtime algorithm.
We can optimize this to run in $O(C)$ time by only keeping track of the previous state. However, this means we cannot reconstruct the solution with backtracking.
The following modifications are be made: we can include an item multiple times as long as we are within our capacity. This does not put any upper bounds on the number of times an item may be selected (so this is the unbounded variant of the problem).
The modification to the problem means that the number of times j we can take an item is at most:
$$ \frac{C}{\lfloor \text{items[n-1].weight} \rfloor} $$
Now, to come up with all possible sub-problems, we need to consider the different cases where we consider taking anywhere from 0 to $\lfloor \frac{C}{W} \rfloor$ number of the item.
Thus, we can write the recurrence as follows:
w = items[n-1].weight
v = items[n-1].value
soln(items[], n, C) = max over j = 0, 1, ..., floor(C/W) {
soln(items[], n-1, C - j * w) + j * v
}
Like with the 0,1 Knapsack Problem, we have $O(nC)$ possible sub-problems (does not change from the 0,1 Knapsack Problem).
However, what does change is the amount of time taken to compute the solution to each sub-problem because we need to look at at most $\lfloor \frac{C}{W} \rfloor$ sub-problems.
The worst case is achieved when $W$ is 1 for all items we are considering (so we need to solve $C$ sub-problems to solve a problem). This means the worst case time complexity comes down to $O(n \times C ^ 2)$.
Here, we are going to consider how we can make the recurrence better. Here, instead of considering the smaller sub-problem as only those with less items involved, we can rewrite it as solving the problem on the same number of items but with a smaller capacity.