Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity BEZ; 。Define: mim∑esif3S1…is.tv=y A(i,v)= :了ΣjeSy=v j∈S otherwise 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 ∈ ℤ+ A(i, v) = min S ⊆ {1,…, i} ∑j∈S vj = v ∑j∈S wj if ∃S ⊆ {1,…, i} s.t. v = ∑ j∈S vj ∞ otherwise
Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B EZ; A(i,v)≌minimum total weight of S≤{l,2,.,i} with total value exactly v .Recursion:forl≤i≤n and 1≤v≤V=∑；y A(i,v)=minA(i-1,v),A(i-1,v-v)+wi for i>1 A(1,)= ifv=v1 Dynamic Programming: O.W. Total time costonom Table size:n×V. ·Output::max{vlA(n,)≤B} Time?
• Recursion: for and for • Output: 1 ≤ i ≤ n 1 ≤ v ≤ V = ∑i vi A(i, v) = min {A(i − 1,v), A(i − 1,v − vi ) + wi} i > 1 A(1,v) = { w1 if v = v1 ∞ o.w. 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 Dynamic Programming: Table size: . Total time cost: . n × V O(nV) Polynomial Time?