Please submit code that can solve the Knapsack Problem using the sample input provided here on Moodle. In other words, given a list of items which each have a (weight, value) pair, find which selection of those items has a total weight less than the capacity of the knapsack and the greatest value. The capacity of the knapsack for these problems is 10 * n (the number of items in the list).

You may also try to implement code to solve the Travelling Salesman problem using the sample input (optional).

I expect that your code will be short enough that you can paste it into the text box. Please make sure it is clear which language it is in, and if there any special instructions to build the code. You are also allowed to submit your code as files if you wish.

It is important that your code is straightforward and easy to read. It does not need lots of comments, as long as it is clear and well labeled.

This is a seminar exercise, so it is intended to help you practice.

[[16, 12], [15, 15], [3, 4], [11, 7]] [[2, 6], [8, 13], [3, 19], [11, 16], [16, 8]] [[3, 18], [10, 14], [2, 6], [17, 6], [5, 1], [15, 12]] [[1, 6], [4, 9], [10, 11], [17, 16], [12, 11], [10, 10], [10, 8]] [[15, 2], [10, 17], [9, 20], [20, 15], [5, 18], [2, 18], [9, 3], [17, 7]] [[2, 5], [13, 1], [11, 7], [6, 8], [20, 3], [13, 7], [16, 17], [11, 3], [10, 17]] [[5, 13], [2, 16], [2, 2], [3, 6], [12, 3], [7, 19], [18, 19], [3, 3], [19, 12], [5, 20]] [[2, 17], [9, 16], [17, 18], [7, 7], [11, 6], [15, 3], [5, 18], [4, 14], [4, 13], [16, 5], [16, 5], [17, 1]] [[13, 19], [10, 5], [8, 6], [9, 15], [17, 19], [5, 12], [2, 4], [20, 18], [4, 16], [13, 3], [12, 14], [5, 12], [13, 16], [13, 15], [4, 4]] [[10, 6], [7, 6], [10, 12], [17, 9], [4, 2], [3, 1], [14, 15], [18, 16], [6, 5], [20, 2], [17, 3], [8, 20], [7, 9], [16, 3], [8, 5], [18, 14], [15, 14], [16, 6], [6, 20], [6, 2]] [[15, 5], [18, 8], [20, 18], [1, 4], [6, 8], [20, 7], [6, 16], [14, 18], [11, 1], [2, 4], [14, 13], [1, 18], [15, 12], [10, 11], [2, 13], [10, 16], [20, 19], [13, 19], [20, 17], [16, 1], [15, 8], [9, 18], [15, 15], [6, 4], [3, 14], [19, 12], [14, 18], [12, 11], [6, 6], [2, 8], [18, 19], [1, 5], [3, 18], [14, 7], [19, 6], [10, 11], [18, 20], [3, 7], [7, 7], [12, 6], [6, 7], [16, 6], [12, 18], [3, 19], [16, 18], [7, 20], [10, 8], [11, 10], [15, 1], [20, 5], [10, 7], [14, 9], [5, 9], [17, 20], [16, 1], [9, 6], [6, 15], [11, 14], [16, 9], [3, 13], [15, 6], [12, 1], [11, 8], [8, 1], [20, 14], [19, 9], [7, 18], [14, 10], [18, 17], [16, 14], [6, 3], [17, 14], [9, 6], [7, 12], [3, 10], [7, 15], [11, 16], [10, 16], [9, 19], [2, 2], [9, 18], [13, 9], [8, 15], [20, 17], [19, 5], [1, 2], [11, 13], [2, 20], [15, 6], [19, 3], [18, 13], [7, 8], [14, 15], [15, 13], [14, 12], [11, 10], [14, 16], [15, 15], [17, 16], [2, 14]]