4. (60 points) a. (20 points) Solve the following case for Knapsack problem: the

Question

4. (60 points)

a. (20 points) Solve the following case for Knapsack problem: the capacity K = 7, 5 items with weights w1 = 2 ;w2 = 8 ;w3 = 6 ;w4 = 1 ;w5 = 1, and profits p1 = 10; p2 = 21; p3 = 15; p4 = 4; p5 = 4. Also show the final two arrays Profit[*][*] and Dir[*][*].

b. (20 points) Consider (a) but with two knapsacks, and both capacities are K . Describe your idea how to solve this problem.

c. (20 points) Consider a generalization of question (a), you have t knapsacks, and all have capacity K . Describe your idea how to solve this problem.

Explanation / Answer

Hii there,

Check this as a hint

Hint:

Concept of Knapsack:

            The knapsack is nothing but a sack where in which we need to place the given items according to the capacity of the knapsack. In case of backtracking we consider the profits but in dynamic programming we consider weights.

Algorithm:

            Bound (CP, CW, K)

            {

                        b=CP, c=CW;

                        for i=k+1 to n dp

                        {

                                    c=c + w [i];

                                    if (c<m) then

                                    b= b + p[i];

                                    else

                                    return b+(1-(c-m)/w[i])*p[i]                             ;

                                    return b;

                        }

            }

Consider:

            CP=Current Profit;       CW=Current Weight; K= Index; m=Capacity of Knapsack;

Example:

            Profits P1=10, P2=10, P3=12, P4=18.

            Weights W1= 2, W2= 4, W3= 6, W4=9;

            m=15;

            n=4;

Tracing:

When, i=1 C=2; b=10;

When, i=2 w[2]=4 so, c=c + w[2] c= 2+4= 6 so c= 6 if 6<15  condition gets true so b=10+10=20;

c=6;

b=20

When, i=3 w[3]=6 so, c=c + w[3] c= 6+6= 12 so c= 12 if 12<15  condition gets true so b=20+12=32;

c=12;

b=32

When, i=4 w[4]=9 so, c=c + w[4] c= 12+9= 21 so c= 21 if 21<15  condition gets FALSE    so b+(1-(c-m)/w[i])*p[i] is 32+(1-(21-15)/9)*18=38

c=21;

b=38;

Here we got the maximum profit as 38.

To obtain this maximum capacity we need to consider the Item 4 first then Item 2 then Item 1 that is 18+10+10 = 38.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

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