Implement the exhaustive and greedy algorithms in a program

(Knapsack) You are on the planning committee for a space voyage, and you have been tasked with determining which combinations of supplies and experiments should be brought on the voyage. There are n total items to pick from, and each one has its own value vi and weight wi, for each i ∈ {1,...n}. Your rocket cannot lift more than a total weight of W > 0.

Your task: Design an exhaustive search algorithm which decides which items to bring, such that these items maximize the total value without exceeding the weight limit W. That is, given W and arrays {v1, v2, . . . vn}, {w1, w2, . . . wn} your algorithm should find a subset K of the total items that maximises k∈K vk (out of all possible subsets of items), and such that k∈K wk ≤ W . Your algorithm should output three things:

• An array K containing the indices of the items you should bring,

• The total value of the items you are bringing: k∈K vk,

• The total weight of the items you are bringing: k∈K wk.

(a) Write your algorithm in pseudocode and determine its efficiency class in terms of Θ(·). This algorithm must be exact: of all possible subsets of items, it must return the absolute best one that fits in the rocket.

(b) Consider a different algorithm which works in the following way: it first finds the highest- value item that fits in the rocket, and it adds that to K. Then, it finds the next-highest- value item that fits in whatever capacity is left, and adds that to K. It repeats this process until there are no more items which will fit in the rocket. This is an example of what is called a greedy algorithm. Write this algorithm in pseudocode and determine its efficiency class in terms of Θ(·).

(c) Does your greedy algorithm solve the problem exactly (always find the best set of items)? If it does, prove it. Otherwise, come up with an input to the problem for which the greedy algorithm gives a worse answer than the exhaustive search algorithm (with whatever values you want for n, W, {vi}ni=1, and {wi}ni=1).

(d) Implement both of these algorithms (exhaustive and greedy) in a programming language of your choice. In all your experiments, let W = 10000. For each1 n from 3 to 15, generate at least 5 random inputs to the algorithm: the values {v1, v2, . . . vn} can be any random positive numbers and the weights {w1,w2,...wn} should be random numbers between 1 and 10000. Run both of your algorithms on each randomly-generated input (don’t throw away an input until you have run both of your algorithms on it!). For each randomly-generated input, compute the following things:

• The time (or number of steps) it takes for each of your two algorithms to terminate.

• The total weight of items selected by each algorithm (this value should never be

more than 10000, because that would violate the weight limit).

• The total value chosen by the exhaustive algorithm, divided by the total value chosen by the greedy algorithm (this value should never be more than 1, because the greedy

can’t do better than exhaustive).

Create three scatter plots, one for each of these bullet points, with n on the horizontal axis. For example, if you generated 5 random inputs for each n, each of your plots should have clusters of 5 dots for each n.

Algorithm C++ Programming

Project ID: #17876703

About the project