Java Reference
In-Depth Information
-
At
u
(
i, j
) either we did not select the
i
-th element and then
u
(
i, j
)=
u
(
i
−
1
,j
), or we selected it and then we need to know the utility of
u
(
i
−
1
,j
−
W
i
)
to compute the total utility
U
i
+
u
(
i
−
1
,j
−
W
i
).
Thus we get the key recurrence relation:
u
(
i, j
)=
u
(
i, j
)=0for
j<W
1
,and
u
(
i, j
)=
U
1
for
j
≥
W
1
,i
=1
, i >
1
.
(9.5)
Solving the knapsack problem by using dynamic programming consists of
building a 2D table of size
n
u
(
i, j
) = max
{
u
(
i
−
1
,j
)+
u
(
i
−
1
,i
−
W
i
)+
U
i
}
×
(
W
+ 1) (starting at weight 0) as follows:
Program 9.14
Dynamic programming for solving the 0-1 knapsack
static void
SolveDP ()
int
i,j;
array=
new i n t
[ nbObjects ] [ weightmax+1];
// initialize the first row
for
(j=0;j
<
=weightmax ; j++)
if
(j
<
weight[0]) array [0][ j]=0;
else
array [0][ j]=utility [0];
// for all other rows
for
(i=1;i
<
nbObjects ; i++)
for
(j=0;j
<
=weightmax ; j++)
if
(j
−
weight [ i ]
<
0) array [ i ][ j]=array [ i
−
1][ j ];
else
array [ i ][ j]=max( array [ i
−
1][ j ] ,
array [ i
−
1][j
−
weight[ i]]+ utility [ i ]) ;
}
}
The result of the optimization reads at the bottommost right cell of this array:
u
(
n, W
). To illustrate this algorithm, consider the following input:
static int
nbObjects=8;
static int
[] weight=
{
2,3,5,2,4,6,3,1
}
;
static int
[] utility =
{
5 ,8 ,14 ,6 ,13 ,17 ,10 ,4
}
;
static int
weightmax=12;
static int
[]
[] array;
Then procedure
SolveDP
builds and gets the table of
u
(
i, j
) evaluations (see
Table 9.1).
We now retrieve the solution from the table by beginning from the bottom
right cell: here, a maximum utility score of 38 for
i
=
n
=8.If
u
(
i, j
) has the
same score as the precedent row
u
(
i
1
,j
) then we deduce that object
O
i
was
not chosen. Otherwise, that means that we chose object
O
i
. Starting from the
−
Search WWH ::
Custom Search