Paradigms for Optimization Problems - A Concise and Practical Introduction to Programming Algorithms in Java - page 208

for ( int i=0;i < nbsubsets ; i++)
for ( int j=0;j < nbelements ; j++)
incidenceMatrix [ i ][ j]= false ;
void SetSubsets( int [] [] array)
for ( int j=0;j < array . length ; j++)
{ for ( int i=0;i < array [ j ]. length ; i++)
incidenceMatrix [ j ][ array [ j ][ i ]]= true ;

}
void Display ()
for ( int i=0;i < nbsubsets ; i++) {

for ( int j=0;j < nbelements ; j++)
if (incidenceMatrix [ i ][ j ]) System. out . print ( "1" );
else System . out . print ( "0" );
System . out . println ( "" );
}

}
}

The greedy algorithm described above needs:

1. To find the set covering the greatest number of (not yet covered) elements,

2. To update the boolean incidence matrix once a maximal set of S has been

chosen.

We implement these basic operations by inserting the following code in the
body of class SetCover .

Program 9.11 Basic operations for supporting the greedy algorithm
// Number of covered element by subset i
int Cover( int i)
int nbEl=0;
for ( int j=0;j < nbelements ; j++)
if (incidenceMatrix [ i ][ j ]) ++nbEl;
return nbEl ;
}

// Report the current largest subset
int LargestSubset ()
int i , nbel , max,

select ;

max= − 1; s e l e c t = − 1;
for (i=0;i < nbsubsets ; i++)
{ nbel=Cover( i ) ;
if (nbel > max)

{ max=nbel ; select=i ; }