http://en.wikipedia.org/wiki/Knapsack_problem
The most common problem being solved is the 0-1 knapsack problem, which restricts the number xi of copies of each kind of item to zero or one.
Mathematically the 0-1-knapsack problem can be formulated as:
Let there be 
items, 
to 
where 
has a value 
and weight 
. 
is the number of copies of the item , which, mentioned above, must be zero or one. The maximum weight that we can carry in the bag is W. It is common to assume that all values and weights are nonnegative. To simplify the representation, we also assume that the items are listed in increasing order of weight.
items, to where has a value and weight . is the number of copies of the item , which, mentioned above, must be zero or one. The maximum weight that we can carry in the bag is W. It is common to assume that all values and weights are nonnegative. To simplify the representation, we also assume that the items are listed in increasing order of weight.- Maximize
subject to
Maximize the sum of the values of the items in the knapsack so that the sum of the weights must be less than or equal to the knapsack's capacity.
The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number of copies of each kind of item to an integer value 
.
of copies of each kind of item to an integer value .
The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on is that it is a non-negative integer.
is that it is a non-negative integer.
f[i][v]=max{f[i-1][v],f[i-1][vc[i]]+w[i]}
if only an array f [0 .. V], f [v] after the end of the i th cycle can not guarantee that the state is defined f [i] [V]? f [i] [v] by f [i-1] [v] and f [i-1] [vc [i]] recursion from two sub-problems, can guarantee in the push f [i] [v ] (i.e., the main loop in the i th push f f [i-1] [v] and f [i-1] [v]) can be obtained [vc [i]] value? In fact, this request each time the main loop the push f [v] v = V. .0 order, so as to ensure f [vc [i] the push f [v]] save state f [i -1] [vc [i]] value. The pseudo-code are as follows:
for i = 1 .. N for v = V. .0 f [v] = max {f [v], f [vc [i]] + w [i]};
Meet-in-the-middle
"meet-in-the-middle" is exponential in the number of different items but may be preferable to the DP algorithm when 
is large compared to n. In particular, if the are nonnegative but not integers, we could still use the dynamic programming algorithm by scaling and rounding (i.e. usingfixed-point arithmetic), but if the problem requires 
fractional digits of precision to arrive at the correct answer, will need to be scaled by 
, and the DP algorithm will require 
space and 
time.
is large compared to n. In particular, if the are nonnegative but not integers, we could still use the dynamic programming algorithm by scaling and rounding (i.e. usingfixed-point arithmetic), but if the problem requires fractional digits of precision to arrive at the correct answer, will need to be scaled by , and the DP algorithm will require space and time.