we will come up with a way to solve the 0/1 variant of the problem, so-called because it enforces another rule: The thief may only take one or none of each item. (View Highlight)
a powerset of a set (in our case, the set of items) has 2^N different possible subsets (View Highlight)
Instead of solving a problem outright with a brute-force approach, in dynamic programming one solves subproblems that make up the larger problem, stores those results, and utilizes those stored results to solve the larger problem. (View Highlight)
to solve the problem for a knapsack with a 3-pound capacity and three items, we can first solve the problem for a 1-pound capacity and one possible item, 2-pound capacity and one possible item, and 3-pound capacity and one possible item. We can then use the results of that solution to solve the problem for 1-pound capacity (View Highlight)
and two possible items, 2-pound capacity and two possible items, and 3-pound capacity and two possible items (View Highlight)
