====== 6.4 Subset Sums and Knapsacks: Adding a Variable ====== \\ ====== The Problem ====== \\ >>>>>>>>>>>>>>>>>>> Given n objects and a "knapsack"\\ >>>>>>>>>>>>>>>>>>> Item i weighs w_i > 0 kilograms and has value v_i > 0\\ >>>>>>>>>>>>>>>>>>> Alternative: jobs require w_i time\\ >>>>>>>>>>>>>>>>>>> Knapsack has capacity of W kilograms\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Alternative: W is time interval that resource is available\\ >>>>>>>>>>>>>>>>>>> Goal: Fill in the knapsack so as to maximize the total value.\\ ====== Designing the Algorithm ====== \\ ** False Start: ** \\ >>>>>>>>>>>>>>>>>>> OPT(i) = max profit subset of items 1,…, i\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Case 1: OPT does not select item i:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT selects best of { 1, 2, …, i-1 }\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Case 2: OPT selects item i\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Accepting item i does not immediately imply that we will have to reject other items: It implies that there are no known conflicts\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Without knowing what other items were selected before i, we don't even know if we have enough room for i\\ \\ ** Better solution** >>>>>>>>>>>>>>>>>>> OPT(i, w) = max profit subset of items 1,..., i with weight limit w\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Case 1: OPT does not select item i:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT selects best of { 1, 2, …, i-1 } using weight limit w\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Case 2: OPT selects item i:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> new weight limit = w – w_i \\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT selects best of { 1, 2, …, i–1 } using new weight limit, w – w_i\\ >>>>>>>>>>>>>>>>>>> So, OPT(i,w) is:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 0 if i =0\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT(i-1,w) if w_i > w\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> max{OPT(i-1,w), v_i + OPT(i-1,w-w_i)} otherwise\\ \\ ====== Algorithm ====== >>>>>>>>>>>>>>>>>>> Input: N, w_{1M/sub>,…,w_N, v₁,…,v_N\\
>>>>>>>>>>>>>>>>>>> for w = 0 to W: O(W) time\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[0, w] = 0\\
>>>>>>>>>>>>>>>>>>> for i = 1 to N: --> For all items\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> for w = 1 to W: --> For all possible weights( So O(NW) time\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if w_i > w : --> item's weight is more than available\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[i, w] = M[i-1, w]\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> else:\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[i, w] = max{ M[i-1, w], vi + M[i-1, w-wi] }\\
>>>>>>>>>>>>>>>>>>> return M[n,W]

** Algorithm Analysis**
\\
* The algorithm takes Θ(nW) time to compute the optimal value of the problem.
* Given a table M of the optimal values of the subproblems, the optimal set S can be found in O(n) time.
* Thus the Knapsack Problem can be solved in O(nW) time.

I give this section an 8/10.}