In: Advanced Math
Show that the worst-case number of entries computed by the refined dynamic programming algorithm for the 0-1 Knapsack problem is in Ω(2n). Do this by considering the instance in which W = 2n −2 and wi = 2i−1 for 1 ≤ i ≤ n.
Please answer with clear explanations!!!
Excerpt From: Richard Neapolitan. “Foundations of Algorithms.”