Instance:n items i=1,2,...,n; weights wi,,wn∈Z+；valuesv1,.,yn∈Zt; knapsack capacity B E; 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); ·Complexity:OnV/k)=O(n2vmax/k） V=∑，y:≤nVmax Approximation ratio: SOL nk nk SOL≥OPT-nk → ≥1- ≥1- OPT OPT Vmax WLOG,assume:OPT Vmax maxiViDP 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 ∈ ℤ+ • Complexity: • Approximation ratio: • WLOG, assume: O(nV/k) SOL ≥ OPT − nk OPT ≥ vmax = maxi vi V = ∑i vi ≥ 1 − nk vmax = O (n2 vmax/k) ≤ nvmax SOL OPT ≥ 1 − nk OPT ⟹