Suppose that we have a knapsack with total capacity of W kg. We also have n items where item j has mass wj. The knapsack problem asks for a subset of these n items with the largest possible total mass not exceeding W.
a) Devise a brute-force algorithm for solving the knapsack problem.
b) Solve the knapsack problem when the capacity of the knapsack is 18 kg and there are five items: a 5-kg sleeping bag, an 8-kg tent, a 7-kg food pack, a 4-kg container of water, and an 11-kg portable stove.