The knapsack problem is a well known, that when solved with a backtracking approach, has exponential complexity. In this problem, you are given n items, each with item having a dollar value and a weight. The knapsack can carry a maximum weight W. The algorithm selects the subset of items with maximum value where the sum of the weights of the items does not exceed W.

Task 1: Develop pseudocode for 0-1 Knapsack

Develop pseudocode that solves this version of the knapsack problem (commonly known as the 0-1 knapsack problem, since you either take an item or do not take an item). This should be a backtracking approach with recursion.

Submit this as a text file (cs412_knapsack_01pseudo.txt). It is OK if this code does not compile, but it should be fairly close.

Task 2: Code fractional knapsack problem

The fractional knapsack problem allows items to be broken into smaller pieces so that the total value of the items in the knapsack can be maximized as discussed in class. Your method should run in O(n lg n) time. Submit this as a text file (cs412_knapsack_fractional.py).

Input

Your input will begin with a single line containing a nonnegative integer weight w. This is followed by a single line contains a nonnegative integer n followed by exactly n lines each of which contains a triple (String, real, real). The first String is the item's name, the second is the dollar value of the item and the third is the item's weight.

Output

You should output exactly 2 lines. The first line is the list of items in the knapsack with the value and amount (weight) of each item formatted as shown. The order of the items should follow the ratio of the most expensive per unit weight. The second line is the total value of the items in the knapsack.

Sample Input	Sample Output
11 3 ring 100 5 gold 50 10 silver 50 5	ring(100.00, 5.00) silver(50.00, 5.00) gold(5.00, 1.00) 155.0

Hints:

Python's sort function accepts a lambda function to select which item to use in sorting. So, if you read in the input as a list of lists, it is possible to run the sort on this with a single line of code.

Task 3: Reflect on these problems

Reflect on the problems in task 1 and task 2.

Which problem is more efficient to solve, the 0/1 knapsack or fractional knapsack? Use big-OH complexity to justify your answer.
How would the greedy item selection strategy work for the 0/1 knapsack problem? Reflect on 1) whether this approach would yield the optimal answer and 2) How would its the approaches efficiency/speed be impacted (when compared to the backtracking 0/1 approach)?
For the two questions above, give an example input to support your description? Your input should be specified in the same format as the input to Task 2.

Attach the answers to these question at the end of cs412_knapsack_01pseudo.txt file.

Rubric:

3 points -- Pseudo code for 0-1 knapsack problem
5 points -- code runs and passes Gradescope tests
3 points -- answers to reflection questions in Task 3
1 point -- instructor review

Submit

Submit both files to Gradescope.

cs412_knapsack_01pseudo.txt (submit this to Gradescope too and it should contain both Task 1 and Task 3 work)
cs412_knapsack_fractional.py