Q.4: Explain the memory function method for the Knapsack problem and give the algorithm.
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
//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
//Output: optimal solution subset
if (tablel [ i , j] < 0) then
if (i < w[i]) then
value = Mem_Fun_knapsack(i-1, j)
v[i] + Mem_Fun_knapsack(i-1, j - w[i]))