cs209 lab10

cs209 lab10

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l10.html

For this lab you should submit 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).
The above material should be uploaded to BLACKBOARD before the deadline of 5pm Wednesday 4th. April 2012. You will lose 20% for each day (or part of day) the lab is late. (In BLACKBOARD, you should attach your PYTHON program under "Attach File" in the section "2. Assignment Materials". If you are including anything other than PYTHON code, e.g. answers to questions, etc, it can be cut/pasted in to "Submission" under "2. Assignment Materials".) If any of this is unclear, you should ask the Teaching Assistant in the lab.
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 the greedy strategy.

(Please see lab6 for a description/definition of the original 0/1 Knapsack problem.)
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). In the one PYTHON program, you should solve this problem using greed based on

maximizing the value

minimizing the weight

maximizing the ratio of value/weight

Note:

You can read the data in from the user using input(): ask for the bag capacity, the list of values, the list of weights.
Your answer should say both
1. which items to pick
2. the total resulting value obtained

Run your program 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. Submit all 9 answers (the 3 different greedy approaches used for each of the 3 different bag capacities) with your report.