Problem 1
Our dynamic knapsack uses memorisation and tabulation to ensure there is no repeated calculations.
Problem 2
Our Mknapsack function gets the maximum of the value parameter, and returns that value and list of names pair. We do this by defining a maximum’ function that uses maximumBy with our ordering function compareFirst, which we use to compare on the value parameter.
Problem 3
Our bknapsack function recursively goes down the list one element at a time, which makes sure that elements aren’t picked more than once. We compare the value of the knapsack for each element for if we add it then continued recursing or if we don’t add it, and pick option that results in the highest value.
We get the option with the highest value using our maximum’ function again to compare on values, and return this.
This solution takes O(2^n) time as an element can either be in the knapsack or not, which has 2^n combinations.
Problem 5
This problem is very similar to the previous one, instead just getting the element from an array using the index we keep track of, rather than from  recursing into the list structure. This is very similar to the previous option as we still go through wvs element by element, which avoids duplicate elements in the knapsack. We chose to implement this as starting from the length of wvs – 1, going down to 0, going through all the elements in reverse order.
This solution takes O(2^n) time as a element can either be in the knapsack or not, which has 2^n combinations.
Problem 6
We now use tabulate to construct the table that we lookup with our index I to go through all of the elements. This is an example of divide and conquer, and means we don’t have to compute duplicate values