Answer Happy

Part A (16 pts): In lecture we saw the Knapsack: Dynamic Programming II (KNAPSACK II) framework, which is an optimization problem where we are given a set S of n items, each with an associated integral weight and a profit Wi, Vi, respectively. With this, we seek to find a subset S' CS such that sies W; is minimized and [sies' Vi = V for an arbitrary integer V. (On a side note, this formulation was related to the original Knapsack framework (KNAPSACK I) from module 5 by setting V = V* where V* is the largest V such that LS, ES W; 5 W for an arbitrary integer W ). One could formulate the decision version of KNAPSACK II by including an additional integer W, and asking whether there exists a subset S' C S such that Es;es V; = V and Es; Esi W; S W. As seen in lecture (and by many of you in midterm exam 2), the SUBSET-SET problem is a seemingly related decision problem where we are given a set of k integers and an arbitrary integer X. For these we ask whether there exists a subset Z' < Z such that <z;€Z! Zi = X. Assume that SUBSET-SUM IS NP-Complete, and use this to show that the decision version of KNAPSACK II is NP-Complete. Of the three reduction strategies seen in lecture, which one did you use? Explain. Part B (6 pts): Is the optimization version of KNAPSACK II NP-Complete? Either prove this is the case, or argue why the problem may not be NP-Complete. You may cite your answer to part a in your response if necessary. Part C (6 pts): Give a description of a 3-approximation algorithm for KNAPSACK 1 (from module 5). Justify correctness and runtime. You may directly cite lecture materials as needed without reproducing them.