array of size to contain the solutions for all subproblems (ik) < < < < there are two approaches to actually solving the problem one is to start with our problem of size (nkand make recursive calls to solve the subproblemseach time checking the array to see if subproblem has been solvedand filling the array whenever we get new subproblem solution the other is to start filling the array for row (which indicates successful solution only for knapsack of size ki we then fill in the succeeding rows from to nleft to rightas follows if ( khas solutionthen (nkhas solution else if ( kn has solution then (nkhas solution else (nkhas no solution in other wordsa new slot in the array gets its solution by looking at two slots in the preceding row since filling each slot in the array takes constant timethe total cost of the algorithm is th(nkexample solve the knapsack problem for and five items with sizes we do this by building the following array / / key-no solution for (ikosolution(sfor (ikwith omitted isolution(sfor (ikwith included /osolutions for (ikwith included and omitted for examplep ( stores value / it contains because ( has solution it contains because ( ( has solution since ( is marked with an iit has solution we can determine what that solution actually is by recognizing that it includes the th item (of size )which then leads us to look at the solution for ( this in turn has solution that omits the th itemleading us to ( at