GREEDY APPROXIMATION ALGORITHM & Knapsack Algorithm
generate some random data, and compare the results. Specific instructions follow:
1. Our basket will hold a weight of 1000. Using a random number generator, generate 100 possible items for the basket. The items should have random weights between 1 and 300.
SUBSET-SUM
Input: n, w1,…,wN,
for w = 0 to W
M[0, w] = 0
for i = 1 to n
for w = 1 to W
if (wi > w)
M[i, w] = M[i-1, w]
else
M[i, w] = max {M[i-1, w], wi + M[i-1, w-wi ]}
return M[n, W]
2. Use the dynamic programming algorithm to compute the exact optimal solution for the set of 100 items. Note that the solution is a weight, wj, where 0 < wj < 1000.
3. Use the greedy approximation algorithm to compute an approximate solution using the same set of items.
4. Run this set of steps 10 times, keeping track of the high, low and average values. Also, keep track of the running times for both algorithms.
This project requires a report. The report should contain a table with your experimental results. The table should look like this, but with your own numbers (my numbers are completely made up and should not be used as a guide):
Dynamic (Exact)
Greedy (approx.)
Approximation Factor
Highest
997
927
93%
Average
823
754
92%
Lowest
742
650
88%
Report
1. An introduction including your approach to the problem, the theoretical time complexity of each subset-sum-finding method used, programming language used and how this might affect the results, problems encountered, etc.
2. A proof that the greedy algorithm is guaranteed to fill the knapsack at least half full.
3. The table with results, as shown above.
4. A discussion of the results, how close they are to each other, and whether the greedy algorithm always fills the knapsack at least half full.
5. A discussion of the running times. Include a table if it will help. How much faster is the greedy algorithm?
Hey!
I'm Vladimir, Computer Science student at the University of Cambridge. I'm totally familiar with all the stuff you have mentioned in the project and I can assure you to do the job fast and neat.
Looking forward to collaborating!
Vladimir
Hi! This task lies in my area of expertise. I have a complete understanding of the task and can guarantee a final solution in 2 days.
This a typical task that asks to implement well known algorithms, so it shouldn`t cause any substantial effort and reporting is also looks quite standard.
Hello,
I read your project requirement carefully and get complete idea about it.
I am computer science engineer able to do this job using my dynamic, greedy programming skills.
Ping me for further discussion.
Thank You.