cs209 lab6

cs209 lab6

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l6.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 Tuesday 11th. March 2014. 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 dynamic programming strategy. 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 the dynamic programming strategy. Your program should build up the table (list of lists) of subsolutions, and not use a recursive function. Instead, just use nested loops.
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.

Check in the input that

None of the input numbers are negative.
The list of values is of the same length as the list of weights.

Your answer should say both

which items to pick
the total resulting value obtained

Run your program on the data:

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

and bag capacities 48kg, 71kg and 103kg, and submit these 3 answers with your report.