Problem (10 points):
In Tutorial 3 Problem 2, we worked on the knapsack problem in which there is only one unit of every item i. Here we consider the version where there is an unlimited supply of every item. In this version, we can consider a dynamic programming formulation for computing this quantity: K(x), which is defined as the maximum value achievable with a knapsack of capacity x.
(a) Please try to give a recurrence for K(x)?
(b) Please try to write up the computing procedure for K(x).
(c) What is the estimated running time (in terms of n and W)?
(d) Please draw a graph (with directed links) to illustrate the computation (just like the one I showed you in Tutorial 3 and in Tutorial 1 follow-up). How would you describe the computation using this graph?
Nice one.I have this topic in my syllabus can you provide a link where I can find a more detailed information on this from examination point of view.Thanks PDF signature
ReplyDelete