Q.4: Explain the memory function method for the Knapsack problem and give the algorithm.

Answer:

**Memory Functions**

While solving recurrence relation using dynamic programming approach common subproblems may be solved more than once and this makes inefficient solving of the problem. Hence memory function is a method that solves only necessary subproblems. Hence we can define the goal of memory function as : solve only subproblems that are necessary and solve these subproblems only once.

Memorization is a way to deal with overlapping subproblems in dynamic programming. During memorization -

1. After computing the solution to a subproblem, store it in a table.

2. Make use of recursive calls.

The 0-1 Knapsack Memory Function Algorithm is as given below -

Globally some values are to be set before the actual memory function algorithm

for (i = 1 to n) do

for (j=1 to W) do

tablel[i,j] = -1

for (j=0 to W) do

table[0,j]=0

//making oth row 0

for i=1 to n do

table[i,0]=0 //making oth column 0

Algorithm Mem_Fun knapsack(ij)

//Problem Description: Implementation of memory function method

//for the knapsack problem [/Input: i is the number of items and j denotes the knapsack's

//capacity

//Output: optimal solution subset

if (tablel [ i , j] < 0) then

{

if (i < w[i]) then

value = Mem_Fun_knapsack(i-1, j)

else

value-max(Mem_Fun_knapsack(i-1, j)

v[i] + Mem_Fun_knapsack(i-1, j - w[i]))

tablel[i,j]=value

}

return table[i,j]

notes For Error Please Whatsapp @9300930012