^   r x Top- f^O^IW
10== o •■
fcôUQM 1 /ao feéToQKl T' m C*»-1) ? ti m(N-l) ~
-2
SuÄSToíi o Cm)
A I
S
Tl
/I
2
r
i-
opi G,^V AoříC'-",^
t
[
Knapsack («, W, wi,    wn, v\,
For w = 0 to W M[Q, w] <- 0
For í =1 to n Č M/
For w = 1 to
opro-Tw) ifw,>w
max{ OPT(i-1, w), vŕ + OPT(i-l,w-w;)} otherwise
If (wi>w) M[z, w] <— M[i-l,w].
Else        A/[ i, w] «— max {M[ i -1, w], vr + M[ i-1, w - w/] }.
Return A/[n, řT].
Knapsack algorithm demo
subset of items
1, .... i
Vi
Wt
{1,2}
{ 1, 2, 3 }
{ 1, 2, 3,4}
{ 1, 2, 3, 4, 5 }
1	1	1		lo	if jTo^
2	6	2	OP7\/,w) = .	QPT(i-l,w)	if Wj>W
3	18	5		max{ OP2*(í-1, w),  v, + OPT(i -1, w- w,-) ]	• otherwise
4	22	6			
5	28	7		weight limit w	
1 1
	
0	0
1	1
5        6        7        8 9
0        0 0
inn
18      22      24      28      29 2!
0 1
6        7        7       18      22      28      29      34      3$| @ OPT(i, w) = max profit subset of items 1, .... i with weight limit w.
6-* o