Java Reference
In-Depth Information
}
Compiling and running this program, we obtain the well-known 92 distinct
solutions that are displayed in the console using a 2D binary matrix indicating
the queen locations as shown below:
...
00000001
00100000
10000000
00000100
01000000
00001000
00000010
00010000
00000001
00010000
10000000
00100000
00000100
01000000
00000010
00001000
Total number of solutions:92
It turns out that only 12 of these solutions are non-naive since others can
be deduced from this reduced set of solutions by using rotation, flipping or
symmetry operations. You can try the program on any arbitrary chessboard
size, say of width size
n
= 10, and observe the number of solutions (724 distinct
configurations for
n
= 10).
9.3 Greedy algorithms: Heuristics for
guaranteed approximations
9.3.1 An approximate solution to the 0-1 knapsack
problem
We revisit the former filling knapsack problem of
ยง
9.2.1 where we are given
aset
of
n
objects
O
1
, ..., O
n
called items and a knapsack to fill up to its
maximal weight capacity
W
. But this time we consider that each object
O
i
,
besides its weight
W
i
, has yet another attribute:
U
i
, its
utility
. The 0-1 knapsack
O
Search WWH ::
Custom Search