A1.(40 points)a. Apply the dynamic programming algorithm to the followinginstanc

Question

A1.(40 points)a. Apply the dynamic programming algorithm to the followinginstance of the 0-1 knapsackproblem:

capacity W= 6.Show your pseudo codes for the dynamic programming solution. You shouldinclude a procedure to retrieve an optimal solution.

b. How many different optimal subsets does the instance of part (a) have?

c. In general, how can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal subset for the knapsack problem’s instance?

Explanation / Answer

In 0-1 knapsack problem each item must be entirely accepted or rejected.We can choose the weights in such a way that they will give max value and should be greater than or equals to the requird weight(here it is 6).Consider the bottom up manner to fill the table,

a)

Pseudo code:

Consider k[n,w] be the knapsack of maximum items and weights.

define W, wt[], val[], n //wt[] be the weights,val[] be the values,n be the no of item

   int K[n+1][W+1];// knapsack matrix

// Build table K[][] in bottom up manner

   for (i = 0; i <= n; i++)

   for (w = 0; w <= W; w++)

if (i==0 || w==0) // not considering any item and weight

               K[i][w] = 0;

           else if (wt[i-1] <= w) //if we consider the weight less than or equals to given weight

                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);

           else

                 K[i][w] = K[i-1][w];

   return K[n][W];

Here we should carefully choosen the items that gives maximum value with required weight .

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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