For the 0-1 Knapsack problem, let K(w, j) denote the maximum value achievable us
ID: 3574828 • Letter: F
Question
For the 0-1 Knapsack problem, let K(w, j) denote the maximum value achievable using a knapsack of capacity w and items from 1, ..., j. Give a recurrence relation for K(w, j) together with boundary conditions K(0, j) and K(w, 0). Let U = {u_1, u_2, u-3, u_4} and C = {{u_1, u_2, u_4}, {u_2, u_3, u_4}}. Use the reduction from 3Sat to Vertex Cover given in class to construct from (U, C) its corresponding instance (G, k). Establish the NP-hardness of the problem of determining whether a weighted graph G = (V, E;w) with w: E rightarrow Z^+ contains k vertices V' such that for every pair of vertices in V', their distance in G is at most d epsilon Z^+.Explanation / Answer
(e)
K(w,p) = max(K(w-w[p],p-1),K(w,p-1)) for any 0<p<=j and w>=w[p]
or
K(w,p) = K(w,p-1)for any 0<p<=j and w<w[p]
(w[p] represents the weight of the jth item)
K(0,j) is 0 and K(w,0) is 0.