Instance:n items i=1,2,...,n; weights wi,,wn∈Z+；valuesv1,,yn∈Zt; knapsack capacity B E; ·For arbitrary0<e<l: DP with truncated precision: Set k=c.Vmax/n where Vmax maxiV; for i=1.2,...,n:letv=v/k; return the knapsack solution found by DP using new values v(but old weights w;and capacity B); pey0a因=o(9） FPTAS Approximation ratio: 1 OPT max Are FPTASs the "best"approximation algorithms?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: FPTAS } Are FPTASs the “best” approximation algorithms?