Java Reference
In-Depth Information
problem is a packing problem where one seeks for the best selection of objects
such that:
1. the overall sum of the selected objects is less or equal to the knapsack
capacity
W
,and
2. the overall utility of selected items is
maximized
.
This can be written mathematically as the following optimization problem:
max
U
i
,
(9.1)
I
⊆{
1
,...,n
}
i
∈
I
such that
i
W
i
≤
W.
(9.2)
∈
I
Figure 9.2 depicts an instance of the optimization knapsack problem.
2
e
5
e
3kg
12 kg
???
Knapsack:
Capacity
14
kg
7
e
???
1
e
5kg
2kg
10
e
4kg
Figure 9.2
The 0-1 knapsack problem consists of finding the set of items that
maximizes
the overall utility while fitting the knapsack capacity
Exhaustively checking all 2
n
(power sets 2
O
)aswedidbefore
takes too long and faces intrinsic limitations as soon as
n
subsets of
O
40, due to
the exponential size of the configuration space. We prefer to design a
heuristic
for the task that will report not an exact solution, but rather a guaranteed
approximation. The basic idea of the greedy algorithm is to first choose the
object
O
l
that maximizes the ratio
G
l
=
∼
30
−
U
i
W
i
of utility
U
l
over its weight
W
l
,
remove this object from the set of items, and repeat until we reach the maximum
capacity
W
of the knapsack, or when we cannot add any more objects without
Search WWH ::
Custom Search