USING JAVA

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible [Wikipedia].

Please analyze the problem and find the recursive solution showing the optimal substructure.

Please design your own dynamic programming algorithm and analyze its running time.

Please use Java to implement your algorithm.

Please test your program with different input and record the results.