**Problem Statement
**A thief robbing a store and can carry a maximal weight of
*W *into their knapsack. There are n items and *i ^{th }* item
weigh

There are two versions of problem

Fractional knapsack problemThe setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction ofxof item_{i}i, where 0 ≤x≤ 1._{i}

0-1 knapsack problemThe setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.

**Fractional knapsack problem**

- Exhibit greedy choice property.

Þ Greedy algorithm exists. - Exhibit optimal substructure property.
- Þ

**0-1 knapsack problem**

- Exhibit No greedy choice property.

Þ No greedy algorithm exists. - Exhibit optimal substructure property.
- Only dynamic programming algorithm exists.

Let *i* be the highest-numbered item in an optimal solution
*S *for
*W* pounds. Then *S**`
*= *S* - {*i*} is an optimal solution for
*W - w _{i
}*pounds and the value to the solution

We can express this fact in the following formula:
define *c*[*i, w*] to be the solution for items 1,2, . . . , *i*
and maximum weight *w*. Then

0 if i= 0 orw= 0c[i,w] =c[ i-1,w]if w_{i }≥ 0max [ v_{i }+c[i-1,w-w],_{i}c[i-1,w]}if i>0 andw≥w_{i}

This says that the value of the solution to *
i *items either include
*
i ^{th} *item, in which case it is

Although the 0-1 knapsack problem, the above formula for *c* is similar
to LCS formula: boundary values are 0, and other values are computed from the
input and "earlier" values of *c*. So the 0-1 knapsack algorithm is like
the LCS-length algorithm given in CLR for finding a longest common
subsequence of two sequences.

The algorithm takes as input the maximum weight *W*, the number of items
n, and the two sequences *v* = <*v _{1}*,

Dynamic-0-1-knapsack (v, w, n, W)FOR

w= 0 TOW

DOc[0,w] = 0

FORi=1 ton

DOc[i, 0] = 0

FORw=1 TOW

DO IFfw≤_{i}w

THEN IFv+_{i}c[i-1,w-w]_{i}

THENc[i,w] =v+_{i}c[i-1,w-w]_{i}

ELSEc[i,w] =c[i-1,w]

ELSE

c[i,w] =c[i-1,w]

The set of items to take can be deduced from the table, starting at
*c*[*n.
w*] and tracing backwards where the optimal values came from. If* *
* c*[*i,
w*] = *c*[*i*-1, *w*] item
*i* is not part of the
solution, and we are continue tracing with *c*[*i*-1, *w*].
Otherwise item *i* is part of the solution, and we continue tracing with* *
* c*[*i*-1,
*w*-*W*].

**Analysis**

This dynamic-0-1-kanpsack algorithm takes
θ(*nw*) times, broken up
as follows: θ(*nw*) times to fill the *c*-table, which has
(*n *+*1*).(*w *+1)
entries, each requiring θ(1) time to compute.
*O*(*n*) time to
trace the solution, because the tracing process starts in row
*n* of the
table and moves up 1 row at each step.