試題詳解

25. The recurrence relation in the previous problem solves the 0-1 knapsack problem in a dynamic programming manner by filling the table of V[i][j]. Which of the following statements is correct about the running time of this algorithm?
(A)It is a linear-t -time algorithm.
(B) It is a polynomial-time algorithm, but not a lincar-time algorithr.
(C) It is an exponential-time algorithm, but not a polynomial-time algorithr.
(D) Nobody knows yet whether or not it is a polynomial-time algorithm.