# 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.

スキル： アルゴリズム, C++プログラミング

( 10件のレビュー ) colorado springs, United States

プロジェクトID: #17876703

## アワード：

bianyunzhi95

Nice to meet you. I've read your project description carefully and I can do exactly what you want. I am a heavily experienced C/C++ developer with strong backgrounds in Algorithm and Data Structure. I am keen on Dyn もっと

\$77 USD 2日以内
(10レビュー)
4.2

## 7人のフリーランサーが、このジョブに平均\$153で入札しています

Piao217

I am an MSc majored in mathematics. I have rich exp in ACM/ICPC and deep understandings of algorithms. I attended at ACM regional contest several times and won medals there. I also have experience in online algorith もっと

\$222 USD 3日以内
(50件のレビュー)
6.5
qingbi53

Hi there,I see you're looking for somebody to Implement the exhaustive and greedy algorithms I am expert in the following C++,C#, .NET,Software Architecture,Windows Desktop etc. I understand exactly what you’re looki もっと

\$200 USD 3日以内
(4件のレビュー)
3.4
hiimsoba

Hello! I am very familiar with greedy algorithms and with the Knapsack problem and can give you a solution in quite short time. I have been solving such problems for the past 4 years and I can provide fast and qu もっと

\$75 USD 2日以内
(2件のレビュー)
2.1
todo2095

hi there, i will be happy to help you, i'm available to start working now, contact me to discuss more.

\$140 USD 5日以内
(3件のレビュー)
1.7
kkc1985612

Hi! I have full experience and expertise knowledge about project like yours. I have been similar project before. You will be satisfy, if you contract with me. Programming Language : HTML5, C++, JavaScript, もっと

\$200 USD 3日以内
(0件のレビュー)
0.0
Alekya115

I have implemented various algorithms in my recent projects and have good knowledge of data structures and algorithms from my masters time. You can even go through my hacker rank page, code fights and leet code.

\$155 USD 3日以内
(0件のレビュー)
0.0