chap patterns of algorithms one solution to the problem is example having solved the previous example for knapsack of size how hard is it now to solve for knapsack of size unfortunatelyknowing the answer for is of almost no use at all when solving for one solution is if you tried solving these examplesyou probably found yourself doing lot of trial-and-error and lot of backtracking to come up for an algorithmwe want an organized way to go through the possible subsets is there way to make the problem smaller to apply divide and conquerwe essentially have two parts to the inputthe knapsack size and the items it probably will not do us much good to try and break the knapsack into pieces and solve the sub-pieces (since we saw that knowing the answer for knapsack of size did nothing to help us solve the problem for knapsack of size sowhat can we say about solving the problem with or without the nth itemthis seems to lead to way to break down the problem if the nth item is not needed for solution (that isif we can solve the problem with the first itemsthen we can also solve the problem when the nth item is available (we just ignore iton the other handif we do include the nth item as member of the solution subsetthen we now would need to solve the problem with the first items on knapsack of size kn since the nth item is taking up kn space in the knapsack to organize this processwe can define the problem in terms of two parameters the knapsack size and the number of items denote given instance of the problem as (nknow we can say that (nkhas solution if and only if there exists solution for either ( kor ( kn that iswe can solve (nkonly if we can solve one of the sub problems where we use or do not use the nth item of coursethe ordering of the items is arbitrary we just need to give them some order to keep things straight continuing this ideato solve any subproblem of size we need only to solve two subproblems of size and so onuntil we are down to only one item that either fills the knapsack or not this naturally leads to cost expressed by the recurrence relation ( ( th( that can be pretty expensivebut we should quickly realize that there are only ( subproblems to solveclearlythere is the potential for many subproblems being solved repeatedly this is natural opportunity to apply dynamic programming we simply build an