Analysis & Design of Algorithms

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