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

exceeding the capacity. This is a greedy approximation heuristic that selects
objects one by one. Once an object is taken it is not considered any more,
and the optimization heuristic proceeds with the remaining objects. A choice
is therefore definitive and irrevocable. The ratio factor of the utility over the
weight is called the gain of objects.
Consider solving a 0-1 knapsack with capacity W = 20 and the following set of
n = 10 (ten) items:

i 123 4 56789 0

U i

538 257923 6

W i 352 4 73235 7

5
3

3
5

43 7

7
3

9
2

2
3

3
5

6
7

G i

Program 9.9 Greedy approximation algorithm for solving the 0-1 knapsack
class GreedyKnapsack
static int n=10;
static int [] W= { 5,3,8,12,5,7,9,2,3,6 } ;
static int [] U= { 3, 5, 2, 4, 7, 3, 2, 3, 5, 7 } ;

static int wKnapsack=20;

// Greedy algorithm for approximating a best solution
public static void main( String [ ] argArray)

double []

gain= new double [n];

double g;
int nSel=0;
int u=0;
int w=0;
int i , winner ;
boolean [] chosen= new boolean [n];

System . out . println ( "Maximum weight of the knapsack:" +
wKnapsack) ;

for (i=0;i < n ; i ++)
gain [ i]=U[ i ]/( double )W[ i ] ;
chosen [ i]= false ;
}

while (nSel < =n && w < wKnapsack)
g=0.0d; winner= − 1;

for (i=0;i < n ; i ++)
{