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

if (!chosen[i] &&w+W[ i ] < =wKnapsack)
System . out . println ( i+ " Weight " +W[ i ]+ " Utility " +U [ i ] + "
Gain[" +i+ "]=" +gain [ i ]) ;

}

// Search best gain in the remaining collection of objects
for (i=0;i < n ; i ++)
if (! chosen [ i ] && gain [ i] > g && wKnapsack − (w+W[ i ] ) > =0)
{ g=gain [ i ]; winner=i ; }

// Can we add this object to the knapsack
if (winner!= − 1&&w+W[ winner] < wKnapsack)
u+=U[ winner ] ;
w+=W[ winner ] ;
chosen [ winner]= true ;
nSel++;
System . out . println ( "Selected object " +winner+ ", updating
#weights=" +w+ " #utility=" +u ) ;

}
else break ;
}

}
}

Running the greedy knapsack heuristic on the set of above items, we get the
following output at the console:

Maximum weight of the knapsack:20
0 Weight 3 Utility 5 Gain[0]=1.6666666666666667
1 Weight 5 Utility 3 Gain[1]=0.6
2 Weight 2 Utility 8 Gain[2]=4.0
3 Weight 4 Utility 12 Gain[3]=3.0
4 Weight 7 Utility 5 Gain[4]=0.7142857142857143
5 Weight 3 Utility 7 Gain[5]=2.3333333333333335
6 Weight 2 Utility 9 Gain[6]=4.5
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 6, updating #weights=2 #utility=9
0 Weight 3 Utility 5 Gain[0]=1.6666666666666667
1 Weight 5 Utility 3 Gain[1]=0.6
2 Weight 2 Utility 8 Gain[2]=4.0
3 Weight 4 Utility 12 Gain[3]=3.0
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 2, updating #weights=4 #utility=17
0 Weight 3 Utility 5 Gain[0]=1.6666666666666667
1 Weight 5 Utility 3 Gain[1]=0.6
3 Weight 4 Utility 12 Gain[3]=3.0
4 Weight 7 Utility 5 Gain[4]=0.7142857142857143