EEEN20010 Computer Engineering I "The Knapsack Problem" (knapsack) You are expected to demonstrate a working C program according to the description below. Your program should be uploaded (via Blackboard) before the deadline. You must use the file names specified in the problem description below. Late submissions will not be corrected and will receive zero credit, so even if your programs are not running correctly, you should submit your "best attempt". Program description One of the classic NP-hard problems is the knapsack problem. In this problem, the objective is to find an "optimal" packing of a backpack which will maximise the total value of the objects in the backpack, without exceeding a weight and cost budget. For example, Table 1 gives a list of items which you might take on a camping trip, together with their weight, cost, and "value" to the user. The goal is to find the selection of items which maximises the total value, while staying within a weight budget of 13 kg and a cost budget of 60 For example, one packing might be Pillow (V=1,W=2, C-6), Tent (V-7,W=6,C=30), Water (V-6,W-5,C-4) which has a total value of 14, weight of 13 kg, and cost of 40 However, a better packing might be Knife (V-8,W=1 , C-10), water (V-6,w:5,C-4), Map (V-5, W=1,C= 15), Tent (V=7, W-6,C-30) which has a total value of 26, weight of 13 kg, and cost of 59 Many NP-hard problems can be "solved" by brute force, if the dimensions of the data set are small. In a "brute force" optimisation, the algorithm evaluates every possible solution, and finds the best solution by checking out the total value, weight and cost of every possible combination