Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1.,yn∈Zt; knapsack capacity B EZ+; DP with truncated precision: Set k (to be determined); for i=1,2,...,n:letv=vk; return the knapsack solution found by DP using new values v(but old weights w;and capacity B); S*:optimal knapsack solution of the original instance or==2是≤k(+1)s2g+k iS* i∈S* i∈S* iES* S:solution returned by the algorithm (optimal solution of the scaled instance) → ∑≥∑ 5oL=≥2=k2y≥2yorM iES i∈S* iES*DP with truncated precision: Set (to be determined); for : let ; return the knapsack solution found by DP using new values (but old weights and capacity ); k = i = 1,2,…, n v′ i = ⌊vi/k⌋ v′ i wi B Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ • optimal knapsack solution of the original instance • solution returned by the algorithm S* : S : OPT = ∑ i∈S* vi= k∑ i∈S* vi k ≤ k∑ i∈S* (⌊ vi k ⌋ + 1 ) ≤ k∑ i∈S* v′ i + nk (optimal solution of the scaled instance) ∑ i∈S v′ i ≥ ∑ i∈S* v′ i SOL = ∑ i∈S vi ≥ k∑ i∈S ⌊ vi k ⌋ = k∑ i∈S v′ i ≥ k∑ i∈S* v′ i ≥ OPT − nk ⟹