We give a dynamic programming algorithm that solves the Knapsack problem in O (nW) time where n is the number of items and W is the capacity of the knapsack. Using similar technique, give an O (nV)-time algorithm for solving the same problem in O (nV) time where V is the sum of the n item values. You may assume that the weights and the values are all integers