Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B E; 。Define: A(i,v)minimum total weight of S {1,2,...,i} with total value exactly v A(i,v)oo if no such S exists Answer to the knapsack problem: max{v|A(n,v)≤B}• Define: • Answer to the knapsack problem: max {v ∣ A(n, v) ≤ B} Dynamic Programming Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ minimum total weight of with total value exactly A(i, v) ≜ S ⊆ {1,2,…, i} v A(i, v) ≜ ∞ if no such S exists