The Complete Rust Programming Reference Guide

The knapsack problem improved

As an example, let's examine the recursive calls of the knapsack solver. For brevity, this knapsack is to be filled using a list of three items where the weight is uniformly one and has a capacity of two. Since the backtracking algorithm walks through the list of items in order (and tries either to include or exclude a particular item), the knapsack solver can be seen as a function K that maps any items that are remaining as well as capacity remaining to a particular value:

Therefore, at the same level, the same input parameter leads to the same value and this is easy to cache. In the preceding diagram, the ...