Scaling Rounding Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B E; DP with truncated precision: Set k=(to be determined); for i=1,2,...,n:letv=vilk; return the knapsack solution found by DP using new values v(but old weights w;and capacity B); Complexity:O(n)=O(nV/k) V=∑， Soundness:the output must be a feasible solution of the original instance since weights and capacity are unchanged.Scaling & Rounding 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 ∈ ℤ+ • Complexity: • Soundness: the output must be a feasible solution of the original instance since weights and capacity are unchanged. O(nV′) = O(nV/k) V′ = ∑i v′ i