Background The Knapsack problem, according to Wikipedia, is one of the most studied problems in combinatorial optimization. The general description of the knapsack problem is the following: Given a set of n items, where each item has an associated profit p_j and a corresponding weight w_j , perform a series of…