Knapsack Problem Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B E; Find an S {1,...,n}that maximizes ∑es subject to∑icsW:≤B. weight6 capacity B weight ·0-1 Knapsack value6 value problem ·one of Karp's21 weight value2 NP-complete problems weights values weight3 OO元eigh value3 value4Knapsack Problem Instance: items ; weights ; values ; knapsack capacity ; Find an that maximizes subject to . n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ S ⊆ {1,…, n} ∑i∈S vi ∑i∈S wi ≤ B weight1 value1 weight2 value2 weight3 weight value3 4 value4 weight5 value5 weight6 value6 capacity B • 0-1 Knapsack problem • one of Karp’s 21 NP-complete problems