Problem 2 [50 points] Consider the following more general version of the Knapsac

Question

Problem 2 [50 points] Consider the following more general version of the Knapsack problem. There are p groups of objects Oi,O2. . . . . Op and a knapsack capacity W. Each object·r has a weight w and a value v Our goal is to select a subset of objects such that: the total weights of selected objects is at most W, - at most one object is selected from any group. and the total value of the selected objects is maximized. Suppose that n is the total number of objects in all the groups and V is the maximum value of any object, i.e., V- max. v Give an (nWime algorithm for this general Knapsack problem. Explain why your algorithm is correct and analyze the running time of your algorithm. Hint: Do a dynamic programming with increasing Knapsack capacity. r is an object

Explanation / Answer

ModifiedKnap_Sack(O, b, W)

for i=1 to p

        sort select the element which vi/wi is maximum and in case of tie wi is minimum

        bi=vi

Aply Knap_Sack(b,W)

     

Knap_Sack(b,W)

for w = 0 to W

        B[0,w] = 0

for i = 1 to n

     B[i,0] = 0

for i = 1 to n

        for w = 0 to W if wi <= w // item i can be part of the solution

if bi + B[i-1,w-wi ] > B[i-1,w]

           B[i,w] = bi + B[i-1,w- wi ]

else

        B[i,w] = B[i-1,w] else B[i,w] = B[i-1,w]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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