CT240 lab9

CT240 lab9

http://geminga.it.nuigalway.ie/~gettrick/courses/CT240/labs/l9.html

For this lab you must submit a printout of all source code (python files), and the result(s) of running the program on (a few) test cases. The source code must be well presented (indenting, spaces, reasonable variable/function names, etc.) and must include comments (as a rough guideline - aim to have nearly as many comments as lines of code). Any questions asked should be answered on a plain sheet of paper.
The above material should be given to Paul or left in the cardboard box marked CT240 in the mail room (room IT415) on the 4th floor of the IT Building before the deadline of 5pm Monday 17th. November 2008. You will lose 20% for each day (or part of day) the lab is late. If you have a genuine reason for submitting a late lab, please contact Paul before the lab due date/time.
Plagiarism (the unattributed copying of work from other sources (internet, fellow students,....)) will not be tolerated. Please see http://www.nuigalway.ie/engineering/documents/plagiarism_guide_students _v4.pdf. You risk getting zero for your lab if it is found to be plagiarized.

In this weeks lab, you should write a program in PYTHON to solve the 0/1 Knapsack problem using a greedy approach. In the 0/1 Knapsack problem, we have a bag of (weight) capacity K kilograms. We have n items of weight w(1), w(2), w(3), ... , w(n) (in Kg) and of respective values v(1), v(2), v(3), ... , v(n) (in euro). We have to decide which items to fit in to our bag to obtain maximum value. There is only one of each item, and you can also assume w(1)+w(2)+w(3)+...+w(n) > K (i.e. all the items won't fit in our bag). Write a PYTHON program to "solve" this using a greedy strategy based on

maximizing the value at each step

minimizing the weight at each step

maximizing the value/weight ratio at each step

Note:

Give the user a "menu" choice of which of the 3 approaches above to use.
You can read the data in from the user using input: ask for the bag capacity, the list of values, the list of weights.
Check in the input that
1. None of the input numbers are negative.
2. The list of values is of the same length as the list of weights.
Your answer should say both
1. which items to pick
2. the total resulting value obtained

Run your program (using all 3 methods in each case) on the data:

WEIGHTS: 21,40,30,3,17,19,26,23,31,7,16,18
VALUES: 40,70,41,6,33,39,48,34,50,15,29,37

and bag capacities 50kg, 80kg and 110kg, and submit these 9 answers with your report.