The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Using Dynamic programing we break the problem down into sub problems (like divide and conquer), except that we keep a record of each sub-problem's solution so that it does not have to be recomputed.