Java Reference
In-Depth Information
Object Weight
0
1
2
3
4
5
6
7
8
9
10
11
12
u
(
i, j
)
1
005555555555 5
2
0
0
5
8
8
13
13
13
13
13
13
13
13
3
0
0
5
8
8
14
14
19
22
22
27
27
27
4
006 8 1 4 4 0 2 5 8 8 3
5
006 8 3 4 9 1 4 7 8 3 5
6
006 8 3 4 9 1 4 7 0 3 6
7
0
0
6
10
13
16
19
23
24
29
31
34
37
8
0
4
6
10
14
17
20
23
27
29
33
35
38
Table 9.1
Table of
u
(
i, j
) evaluations
last row, we thus deduce that we chose
O
8
because 37
= 38; We now
jump
to
u
(
i
W
8
) and proceed similarly until we reach the first row.
The code for retrieving the solution from the 2D table by reading backward is
thus:
−
1
,j
−
Program 9.15
Extracting backward the optimal solution from the 2D table
static void
InterpretArray ()
int
i,u,w;
u=0;
w=weightmax ;
for
( i=nbObjects
−
1;i
>
=1;i
−−
)
{
if
(array [ i ][w]!= array [ i
−
1][w])
{
System . out . print (( i +1)+
""
);
w=w
−
weight [ i ] ;
u=u+utility [ i ];
}
}
if
(array [0][w]!=0) ;
{
System . out . println (
"1"
);
w=w
−
weight[0];
u=u+ u t i l i t y [ 0 ] ;
}
System . out . println (
"Cross check:"
+u+
" remaining weight "
+w ) ;
}
Running this procedure on our toy example, we get:
Reading solution:
87541
Search WWH ::
Custom Search