Java Reference
In-Depth Information
5 Weight 3 Utility 7 Gain[5]=2.3333333333333335
7 Weight 3 Utility 2 Gain[7]=0.6666666666666666
8 Weight 5 Utility 3 Gain[8]=0.6
9 Weight 7 Utility 6 Gain[9]=0.8571428571428571
Selected object 3, updating #weights=8 #utility=29
0 Weight 3 Utility 5 Gain[0]=1.6666666666666667
1 Weight 5 Utility 3 Gain[1]=0.6
4 Weight 7 Utility 5 Gain[4]=0.7142857142857143
5 Weight 3 Utility 7 Gain[5]=2.3333333333333335
7 Weight 3 Utility 2 Gain[7]=0.6666666666666666
8 Weight 5 Utility 3 Gain[8]=0.6
9 Weight 7 Utility 6 Gain[9]=0.8571428571428571
Selected object 5, updating #weights=11 #utility=36
0 Weight 3 Utility 5 Gain[0]=1.6666666666666667
1 Weight 5 Utility 3 Gain[1]=0.6
4 Weight 7 Utility 5 Gain[4]=0.7142857142857143
7 Weight 3 Utility 2 Gain[7]=0.6666666666666666
8 Weight 5 Utility 3 Gain[8]=0.6
9 Weight 7 Utility 6 Gain[9]=0.8571428571428571
Selected object 0, updating #weights=14 #utility=41
1 Weight 5 Utility 3 Gain[1]=0.6
7 Weight 3 Utility 2 Gain[7]=0.6666666666666666
8 Weight 5 Utility 3 Gain[8]=0.6
Selected object 7, updating #weights=17 #utility=43
Here, the maximum utility reported for the input data set is 43. Let
c
∗
denote
the best overall utility of an optimal solution and
c
G
be the overall utility
reported by the greedy algorithm. Then Dantzig proved in 1957 that
c
G
≥
c
2
c
∗
since an approximation can only be worse than an exact
solution). For the 0-1 knapsack problem, we say that greedy approximation
has an approximation factor of 2. Although the greedy heuristic proceeds by
greedily choosing the current best element and reiterating until completion, its
performance factor may vary according to the problem at hand. The following
set cover problem explained in the next section illustrates this important fact.
(of course
c
G
≥
9.3.2 A greedy algorithm for solving set cover problems
The set cover problem (SCP for short) is yet another fundamental combinatorial
optimization problem that arises in many real-world applications. The problem
is defined as follows; We are given a set
X
of
n
elements
X
=
{
X
1
, ..., X
n
}
and
a collection
S
of
m
subsets of
X
:
S
=
{
S
1
, ..., S
m
}
called
ranges
. The goal is to
select a minimum number of sets of
S
so that their union covers all elements
of
. That is, we are asked to solve the following mathematical optimization
problem:
X
Search WWH ::
Custom Search