sec dynamic programming dynamic control systemswhich got its start before what we think of as computer programming the act of storing precomputed values in table for later reuse is referred to as "programmingin that field dynamic programming is powerful alternative to the standard principle of divide and conquer in divide and conquera problem is split into subproblemsthe subproblems are solved (independently)and then recombined into solution for the problem being solved dynamic programming is appropriate whenever the subproblems to be solved are overlapping in some way and if we can find suitable way of doing the necessary bookkeeping dynamic programming algorithms are usually not implemented by simply using table to store subproblems for recursive calls ( going backwards as is done by fibrtinsteadsuch algorithms typically implemented by building the table of subproblems from the bottom up thusfibi better represents the most common form of dynamic programming than does fibrteven though it doesn' need the actual table the knapsack problem we will next consider problem that appears with many variations in variety of industrial settings many businesses need to package items with the greatest efficiency one way to describe this basic idea is in terms of packing items into knapsackand so we will refer to this as the knapsack problem first define particular form of the problemand then discuss an algorithm for it based on dynamic programming we will see other versions of the problem in the exercises and in assume that we have knapsack with certain amount of space that we will define using integer value we also have items each with certain size such that that item has integer size ki the problem is to find subset of the items whose sizes exactly sum to kif one exists for exampleif our knapsack has capacity and the two items are of size and then no such subset exists but if we have add third item of size then we can fill the knapsack exactly with the first and third items we can define the problem more formally asfind { nsuch that ki is example assume that we are given knapsack of size and items of sizes can we find subset of the items that exactly fills the knapsackyou should take few minutes and try to do this before reading on and looking at the answer