cs209 lab5
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l5.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
Monday 6th. March 2017. 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.
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(KG): 23,30,30,4,19,11,24,20,31,9,18,17,15,7
- VALUES(EURO): 40,66,45,7,36,31,48,32,54,14,27,25,32,14
and bag capacities 48kg, 75kg and 91kg,
and submit these 3 answers with your report.
©
NUI, Galway