Generation of Combinatorial Objects · Application: Dynamic Programming (Optional)

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

This is the dynamic programming method for the knapsack problem! The runtime of the resulting algorithm is \(O(W \cdot n)\), where \(n\) is the number of items and \(W\) is the knapsack capacity (the \(\texttt{capacity}\) variable in our code). For many datasets, this bound will be much better than \(O(2^{n})\).

For the curious 🤓

The runtime \(O(nW)\) does not mean that the knapsack problem is solved in time polynomial in the size of the input. In fact, the knapsack problem is NP-hard, so we couldn’t expect such a well-known algorithm to efficiently solve a hard problem. We don’t call an algorithm with \(O(nW)\) runtime fast because the input size is proportional to \(n + \log W\), not \(n + W\). Indeed, we only need \(\log W\) bits to write the number \(W\). A practical view on the same issue: if the decimal representation of \(W\) has, say, 20 digits, then in practice our algorithm won’t finish in any reasonable time.