In the previous sections, we have seen how the knapsack problem can be solved through different approaches. In particular, we learned to treat this problem with an algorithm called brute force: in this case, we obtained the optimal solution at an extremely heavy computational cost. On the other hand, the greedy solution gave us a lighter algorithm from a computational point of view, but did not allow us to obtain the optimal solution. A solution that combines both these needs—an optimal solution and a fast algorithm—can be provided by DP.
As we said in the section on DP, we subdivide an optimization problem into simpler subproblems and store the solution for each subproblem so that each subproblem is solved only once. ...
