Java Reference
In-Depth Information
corresponding weights
W
1
=3,
W
2
=4,
W
3
=5,
W
4
=6and
W
5
= 2. Let us
visualize the input as the following table:
O
i
12345
W
i
34563
The source code for fully exploring the combinatorial space of solutions by
programming nested loops is presented below:
Program 9.1
Plain enumeration using nested loops
class
KnapsackNestedLoops
{
public static void
main( String [ ] argArray)
int
W1= 3 , W2= 4 , W3= 5 , W4= 6 , W5= 2 ;
// respective weights
int
W=11;
// weight capacity of the knapsack
int
bagWeight ;
//
weight of 'current' configuration
for
(
int
i1=0;i1
<
=1; i 1 ++)
{
for
(
int
i2=0;i2
<
=1; i 2 ++)
{
for
(
int
i3=0;i3
<
=1; i 3 ++)
{
for
(
int
i4=0;i4
<
=1; i 4 ++)
{
for
(
int
i5=0;i5
<
=1; i 5 ++)
bagWeight=i1
∗
W1+ i 2
∗
W2+ i 3
∗
W3+ i 4
∗
W4+ i 5
∗
W5 ;
// Does the current selection match the sack
capacity
if
(bagWeight==W)
{
System . out . println (
"Solution:"
+i1+
""
+i2+
""
+
i3+
""
+i4+
""
+i5 ) ;
}
}
}
}
}
}
}
}
Compiling the code (using console command
javac KnapsackNestedLoops.
java
) and executing the above program (using console command
java
KnapsackNestedLoops
), we get
all
possible solutions, reported using
true
/
false
memberships of objects:
Solution:00110
Solution:01101
Solution:10011
That is, the first solution
00110
reads as select object
O
3
and
O
4
(but not
objects
O
1
nor
O
4
): The subset
{
O
3
,O
4
}
of
O
encoded by the index subset
Search WWH ::
Custom Search