Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Z+; knapsack capacity BEZ; Polynomial-time Algorithm A: c >0,V input x,A(x)terminates within O(x)steps x=length of input x(in binary code) Pseudo-polynomial-time Algorithm A: above definition (except x=length in unary code) ER3O0m V=∑ Total timeǒiomia Time!• Polynomial-time Algorithm : , input , terminates within steps length of input (in binary code) • Pseudo-polynomial-time Algorithm : above definition (except length in unary code) A ∃c > 0 ∀ x A(x) O(| x | c ) | x | = x A | x | = Dynamic Programming Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ Dynamic Programming: Table size: . Total time cost: . n × V V = ∑ O(nV) i vi Pseudo￾Polynomial Time!