One form of the knapsack problem is as follows: We are given a set of integers A = a1, a2, . . . , aN and an integer K. Is there a subset of A whose sum is exactly K?
a. Give an algorithm that solves the knapsack problem in O(NK) time.
b. Why does this not show that P = NP?