Prove that the Knapsack Problem (Problem 13.4, Page 550) is in NP.

See Example 13.1 (Page 556) for the (partial) solution to a similar problem. [It would be a complete (rather than partial) solution if they had simply computed the complexity of their 'second phase', and observed that the complexity was bounded by a polynomial.]

Note that your algorithm only is supposed to CHECK a proposed solution, not FIND a solution! Remember to refer to the 'checklist' in the notes and do all FOUR things necessary to show a problem belongs to NP. The notes say: To show a problem belongs to NP, you must do four things: 1) describe the encoding used for the instance 2) describe the encoding used for the certificate 3) describe the algorithm that will check if the certificate is a valid solution 4) analyze the time complexity of that algorithm. If the complexity is (bounded by) some polynomial of the input size, then the problem is indeed in NP

Problem 13.4 Knapsack Suppose we have a knapsack of capacity C (a positive integer) and n objects with sizes .Sn and profits" P.. Pa (wheres.Sn and pi,.... Pa are positive integers). Optimization Problem: Find the largest total profit of any subset of the objects that fits in the knapsack (and find a subset that achieves the maximum profit). Decision Problem: Given k, is there a subset of the objects that fits in the knapsack and has total profit at least k? Problem 13.4 Knapsack Suppose we have a knapsack of capacity C (a positive integer) and n objects with sizes .Sn and profits" P.. Pa (wheres.Sn and pi,.... Pa are positive integers). Optimization Problem: Find the largest total profit of any subset of the objects that fits in the knapsack (and find a subset that achieves the maximum profit). Decision Problem: Given k, is there a subset of the objects that fits in the knapsack and has total profit at least k