CS33200 Algorithms Project

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]. • 0/1 version of the knapsack problem: You can only take or not take each item as a whole. • Fractional version of the knapsack problem: You can cut each item and take any fraction of it.

1. For 0/1 version of the problem. Design an algorithm using dynamic programming. Pseudocode is needed. Will this algorithm achieve optimal solution? 
2. For fractional version of the problem. Design an algorithm using dynamic programming. Pseudocode is needed if it’s different from algorithm in 1. Will this algorithm achieve optimal solution? 
3. For 0/1 version of the problem. Design an algorithm using greedy algorithm. Pseudocode is needed. Will this algorithm achieve optimal solution? 
4. For fractional version of the problem. Design an algorithm using greedy algorithm. Pseudocode is needed if it’s different from algorithm in 3. Will this algorithm achieve optimal solution? 
5. Please use C++ or Java to implement your algorithms in 1, 2, 3, and 4 (if they are different). Submit source code files. 
6. Please test your program with different input and record the results. Submit your test file together with execution results.