Java Reference
In-Depth Information
{
(see Eq. 9.2.1). We check that we indeed have
W
3
+
W
4
=5+6=11=
W
.
Thus the set of solutions can be read back from the bit memberships, as follows:
3
,
4
}
I
∗
=
{{
3
,
4
}
,
{
2
,
3
,
5
}
,
{
1
,
4
,
5
}}
.
The exhaustive search algorithm seeks for all potential solutions by fully
exploring the configuration space. Each configuration is modeled by a set of
“loop indices” telling us whether or not we choose the corresponding object.
This shows that there are 2
n
possible configurations, ranging from the empty
set
1
. Observe
that if we were to add a sixth object, we would need to add another nested loop
directly
inside
the code in order to solve for solutions. This clearly stresses the
limits of the “nested loop” method since we clearly do not want to manually
edit the program source code every time we have a different problem size to
solve. Furthermore, imagine if you were asked to write the nested loop program
for
n
= 100. That would be daunting. Therefore, the number of objects
n
shall
be considered as a parameter of the filling knapsack problem itself.
How do we cope with such a situation? We need to reconsider the configuration
space, and model it appropriately. The potential solution space is modeled by
the
power set
2
O
=
to the complete set
O
, encoded by the full set of indices
{
1
, ..., n
}
{O
,
O
⊆O}
that includes all possible subsets of
O
,
O
⊆O
including the empty set. As highlighted above, to each subset
,we
O
) of length
n
such that the
l
-th bit is set to 1
(or boolean
true
state) if and only if object
O
i
belongs to
associate a binary signature
b
(
O
. The configuration
space is thus in a one-to-one mapping with the space of bit signatures: The
set of binary numbers of
n
bits (with evaluated values ranging from 0 to
2
n
1). In other words, the binary signature depicts the configuration number
whose binary representation is that signature. This shows that the size of the
configuration space is 2
n
;Itgrows
exponentially fast
with
n
. Incrementing
n
doubles the size of the configuration space.
To perform an exhaustive search of the configuration space for any arbitrary
value
n
of objects, we first proceed by enumerating all possible binary
representation numbers with
n
bits. Enumerating all binary representations
with
n
bits can be done using the following recursive algorithms:
−
Program 9.2
Enumerating all 2
n
binary number representations with
n
bits
class
Enumeration
{
static void
display(
boolean
[] tab)
for
(
int
i=0;i
<
t a b . l e n g t h ; i ++)
1
Obviously not a solution since its weight is trivially zero, but nevertheless
considered when browsing the configuration space by these nested loops.
Search WWH ::
Custom Search