cs209 lab7
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l7.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 15th. March 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.
A more general version of the 0/1 Knapsack Problem covered in
lectures and in last weeks lab is the Bounded Knapsack Problem.
In the Bounded Knapsack Problem, there are a number of copies of
each item. In particular, we have n different item types, i=1,2,3,...,n, with
q(1), q(2), q(3), ... , q(n) numbers of each item,
weights w(1), w(2), w(3), ... , w(n) (kg) and
values v(1), v(2), v(3), ... , v(n) (kiloEuro).
(So: The total number of actual items is q(1)+q(2)+q(3)+...+q(n)).
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.
-
Hint 1
You should begin as a basis with the program you wrote last week for
the 0/1 Knapsack problem.
-
Hint 2
Previously - If we denote by prof(i,j) the matrix/table of entries, to
build up this table we used something like
prof(i,j) = MIN(prof(i-1,j),
v(i)+prof(i-1,j-w(i))
) when we were introducing item i. This time, since we may be introducing
multiple copies (up to q(i)) of item i, we pick the minimum of the numbers
prof(i-1,j),
v(i)+prof(i-1,j-w(i)),
2*v(i) + prof(i-1,j-2*w(i)),
3*v(i) + prof(i-1,j-3*w(i)), etc.
[Challenge: What does "etc." mean here? How many copies of item i could we
be introducing here?
Extra Hint:
It cannot be greater than q(i), but also it cannot be greater than
j//w[i] (thats PYTHON code, where // is integer division).]
Note:
-
You can read the data in from the user using input(): ask for the
bag capacity, the numbers of each item, the list of values, the list of weights.
-
Your answer should just state the maximum value that can be obtained.
-
You should test your program on a number of small lists (e.g. 3 items), with
different bag capacities, and numbers q(i), to convince yourself it works.
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
- QUANTITIES: 3,4,2,5,1,1,4,1,3,2,3,6
and bag capacities 50kg, 80kg and 110kg,
and submit these 3 answers with your report.
©
NUI, Galway