Implement the exhaustive and greedy algorithms in a program
$10-30 USD
Completed
Posted over 5 years ago
$10-30 USD
Paid on delivery
(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.
Dear Prospect Hiring Manager.
Thank you for giving me a chance to bid on your project. i am a serious bidder here and i have already worked on a similar project before and can deliver as u have mentioned
I have checked your requirements. We have right skills to work on this assignment. We are a team of professionals including experienced analysts, designers, project managers, developers and QA people having great expertise in web applications development mainly on core PHP, PHP with open sources (Joomla, Wordpress, Codeigniter, Cake PHP), .NET, Asp.NET, Vb.NET, HTML 5 etc. and mobile applications on ios and Android platform.
Our award = superb result = happy client. In a good partnership, good results happen. Good cooking makes good eating!BWe consider our client as our partner.
I am ready to discuss with you
with best Regards