(b) Consider the knapsack problem: the input is a list of n items, each with a value and weight (vali, wt;), and a threshold weight W. All values and weights are strictly positive. The goal is to select a subset S of the items such that Lies wt;