What makes two knapsack nodes the same subproblem, and why does a memo on (items left, capacity left) tame 2ⁿ?
Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.
The given code lists all 17 nodes of the search tree for the four-item menu from the video, each as (items taken, items left, value taken, calories left). Some nodes repeat a subproblem another node already solves. Count how many distinct subproblems the tree contains (a list can't go in a set, but tuple() converts one) and assign the count to distinct.
# Every node of the search tree for menu a(6, 3), b(7, 3), c(8, 2), d(9, 5), budget 5,
# in the order the nodes are generated.
# Each node is (items taken, items left, value taken, calories left).
nodes = [
(set(), ["a", "b", "c", "d"], 0, 5),
({"a"}, ["b", "c", "d"], 6, 2),
({"a"}, ["c", "d"], 6, 2),
({"a", "c"}, ["d"], 14, 0),
({"a"}, ["d"], 6, 2),
({"a"}, [], 6, 2),
(set(), ["b", "c", "d"], 0, 5),
({"b"}, ["c", "d"], 7, 2),
({"b", "c"}, ["d"], 15, 0),
({"b"}, ["d"], 7, 2),
({"b"}, [], 7, 2),
(set(), ["c", "d"], 0, 5),
({"c"}, ["d"], 8, 3),
({"c"}, [], 8, 3),
(set(), ["d"], 0, 5),
({"d"}, [], 9, 0),
(set(), [], 0, 5),
]