We introduced DP in the previous sections. Now the time has come to tackle a practical case. We will do this by analyzing a classic problem that has been studied for more than a century since 1897: the knapsack problem. The first to deal with it was the mathematician Tobias Dantzig, who based the name on the common problem of packing the most useful items in a knapsack without overloading it.
A problem of this type can be associated with different situations arising from real life. To better characterize the problem, we will propose another, rather unique problem. A thief goes into a house and wants to steal valuables. They put them in their knapsack, but they are limited by the weight. Each object has its own value and weight. He must choose the objects that are of value, but that do not have excessive weight. The thief must...