Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values 1,,yn∈Z+; knapsack capacity B E; ·For arbitrary0<e<l: DP with truncated precision: Set k=cVmax/n where ymax maxiV for i=1,2,...,n:letv=vi/k return the knapsack solution found by DP using new values v(but old weights w;and capacity B); .Complexity:(nm= Approximation ratio: ≥1-≥1-DP with truncated precision: Set where for : let ; return the knapsack solution found by DP using new values (but old weights and capacity ); k = ⌊ϵ ⋅ vmax/n⌋ vmax = maxi vi 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: O (n2 vmax/k) = O ( n3 ϵ ) SOL OPT ≥ 1 − nk vmax ≥ 1−ϵ • For arbitrary 0 < ϵ < 1: