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 0-1 knapsack problem

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 unbounded knapsack problem (UKP)

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:

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

Going Faster

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.

Here is how that rewriting of the recurrence looks like:

soln(items[], n, C) = max(
	soln(items[], n-1, C).
	soln(items[], n, C - w) + v
)

This leads to a \(O(nC)\) time complexity because each sub-problem only need \(O(1)\) time to compute.

The bounded knapsack problem

Here, we modify the UKP by setting a limit on the number of copies of how many times we can take the \(i^{th}\) item. This is an additional constraint we add to the problem.

We need to make a minor modification to the solution, where we set a limit on the number of times we consider taking any given element. This means we can write the recurrence as follows:

soln(items[], n, C) = max over j = 0, 1, ..., min(floor(C/W), items[n-1].copies) {
	soln(items[], n-1, C - j * w) + j * v # w is weights, v is value
}

Going Faster

One approach to rethink the problem is to consider the problem as a 0-1 Knapsack problem. If we say that there are at most \(k\) copies of a given element, then we have \(nk\) items.

Using the 0-1 Knapsack algorithm, we get a worst case time complexity of \(O(nk \times C)\).

However, this is not really an improvement because in the worst case \(k\) will be \(C\).

We can do better. The key observation is that the entries we consider are at evenly spaced intervals (where the width of the interval is the weight of the object) so what we need to do is fill up the equivalence classes in the new layer. To do this, we need a data structure that stores \(k+1\) values of the cases where \(0, 1, \dots, k\) copies of that item have been taken.

The idea is that if we have an efficient data structure to maintain a changing set of \(k+1\) values and efficiently extract the maximum value, we can achieve an efficiency improvement.

The idea is to modify a max queue with a function to efficiently add a fixed value to all elements in the queue. The idea is to do this lazily: we store an offset with the property that the actual values in the data structure are the stored values added to the offset.

With this as an invariant, we need to subtract the offset from the value we want to insert before we insert it.

Then, we have a way to perform all the needed operations in \(O(1)\) time.

The fractional knapsack problem

The multiple-choice knapsack problem

With Multiple Constraints

If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiple-constrained knapsack problem, multidimensional knapsack problem, or m-dimensional knapsack problem. (Note, "dimension" here does not refer to the shape of any items.)