Question 1. [10 MARKS In the following let A -[a1,..., an) be a set of n items w

Question

Question 1. [10 MARKS In the following let A -[a1,..., an) be a set of n items where item a, has value vi and capacity ci. Suppose you have a bag with maximum capacity C. We will develop a recurrence relation to find the maximum value obtained by a subset of A whose capacity does not exceed C. Note: this is the classic Knapsack Problem. Many solutions on-line use linear programming or dynamic programming, but this is not what we are asking you to do here; you do not need anything other an the material you learned in class to answer this question. Part (1) 2 MARKS Let T(i, c) be the maximum value obtained after considering the first i items with total capacity c. Come up with an equation for T(0, c) and T(1, c) i.e. what is the maximum value obtained if we considered none of the items? Only consider the first item? Part (2) 3 MARKS Suppose we know T(i, c), the maximum value obtained after considering the first i items with total capacity c. Find an equation for T(i +1,c) in-terms of the values T(i,0), T(i,1),... , T(i, c). Use this equation along with part one to come up with a general recurrence relation for T(k, c). How would we find the maximum value obtained by a subset of A whose capacity does not exceed C1? Part (3) 5 MARKS Suppose we have two bags with capacities C1 and C2 respectively. Let the total profit be the sum of the values of all items in both bags. Find the maximum total profit subject to the capacity constraints as we did for the one bag case above.

Explanation / Answer

Solution:
Part(1):
T(0,c) = 0 as we are not considering any item. So the maximum value obtained will be zero
T(1,c) = v1 as we are considering only the first item. So the maximum value obtained will be the value of the first item

Part(2):
T(i+1,c)=T(i,c) if c<ci+1
ie. If the capacity of (i+1)th item is greater than than the total capacity of first i items then we cant consider that item and hence the above condition holds true.

T(i+1,c)=max(T(i,c),T(i,c-c(i+1))+v(i+1)) if c>=ci+1
ie. If the capacity of (i+1)th item is less than the total capacity of first i items then value of T(i+1,c) will be maximum of T(i,c)ie not considering the i+1 item and T(i,c-c(i+1))+v(i+1)

Part(3):

Now we know the strategy to fill one of the knapsack. Now hen filling two knapsacks, we observe that they are disjoint, so each item can either be placed in one of the knapsacks(if it fits) or will be discarded.

So now we form a Recurrence with an additional parameter for second bag.

Let S(i,c1,c2) denote the maximum possible value we can get by considering first i elements and filling maximum of c1 values in first knapsack and c2 in the second. Now when putting a item in these, we will see three cases.

if c1 + ci+1<=C1
We can put the item in the first knapsack
So this will contribute to
S(i+1,c1+ ci+1,c2)

if c2 + ci<=C2
We can put the item in the Second knapsack
So this will contribute to
S(i+1,c1,c2+ ci+1)

else we cannot do anything.
So this will contribute to
S(i+1,c1,c2)

so in total the recurrence will be

S(i+1,c1,c2)=max(S(i,c1,c2),S(i,c1- ci+1,c2)+vi+1,S(i,c1,c2- ci+1)+vi+1)

while checking for bounds of possibilty
The base cases will be similar to the previous ones

finally we will get the the answer from S(n,C1,C2)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.