The Greedy method is one of the easiest methods of elaborating algorithms and it is used for solving optimization problems. In solving a problem with the greedy method one starts with a possible solution, solution that becomes better along the way, leading to the wanted result step by step.

For easier understanding this method, we will give an example, underlining the essentials of greedy algorithms:

A man reaches a deserted island with his boat. There, he finds more precious metals, a piece of every type. He decides to pick them up and transport them with his boat. He can only take a limited amount of weight in the boat, or else the boat would sink. He can cut the pieces of metal. Not knowing if he will find the metals after a second trip and being a very greedy, the man wants to take home the metals that will give him the biggest profit.

Solution: Let's take a piece of silver and a piece of gold. Although the piece of silver might be worth more than that of gold, it would weigh more. The man isn't interested in taking the piece that is worth the most, but the one that will bring him the best profit. Therefore, we have to decide how profitable a kind of metal is. The profitability of a metal is its value divided by its weight. The vector of profitability must then be ordered decreasingly. The man will take metals from the front of the vector, as long as their weight doesn't exceed the weight limit. The last piece of metal taken can be cut so that it completes the weight that can be added in the boat.

We will have an array with the value, weight, type and profitability of each metal.

Pascal program:

type metal=record
value,weight,metaltype:integer;
profit:real;
end;
var v:array[1..100] of metal;
f,g:text;
maxweight,i,j,k,l,m,n:integer;

procedure readdata;
begin
assign(f,'in.txt');
reset(f);
read(f,n);
for i:=1 to n do
begin
read(f,v[i].metaltype,v[i].value,v[i].weight);
v[i].profit:=v[i].value/v[i].weight;
end;
read(f,maxweight);
end;

procedure sort;
var aux:metal;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if v[i].profit<v[j].profit then begin
aux:=v[j];
v[j]:=v[i];
v[i]:=aux;
end;
end;

begin
readdata;
sort;
k:=0;
i:=1;
assign(g,'out.txt');
rewrite(g);
while (k+v[i].weight<=maxweight) and (i<=n) do
begin
writeln(g,v[i].weight, ' pounds of metal ',v[i].metaltype);
k:=k+v[i].weight;
inc(i);
end;
if i>=n then if k<>maxweight then
writeln(g,maxweight-k, 'pounds of metal ',v[i].metaltype);
close(g);
end

C++ program:

#include<iostream.h>
#include<fstream.h>
struct metal
{
int value,weight,metaltype;
double profit;
};
metal v[100],aux;
int i,j,k,l,m,n,maxweight;
fstream f("in.txt",ios::in),g("out.txt",ios::out);

void readdata()
{
int i;
f>>n;
for (i=1;i<=n;i++)
{
f>>v[i].metaltype>>v[i].value>>v[i].weight;
v[i].profit=v[i].value;
v[i].profit=v[i].profit/v[i].weight;
}
f>>maxweight;
f.close();
}

void sort()
{
for (i=1;i<=n-1; i++)
for (j=i+1;j<=n;j++)
if (v[i].profit<v[j].profit)
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
}

void main()
{
readdata();
sort();
k=0;
i=1;
while ((k+v[i].weight<=maxweight) && (i<=n))
{
g<<v[i].weight<<" pounds of metal "<<v[i].metaltype<<endl;
k+=v[i].weight;
i+=1;
}
if ((i<=n)&&(maxweight-k>0))
{
g<<maxweight-k<<" pounds of metal "<<v[i].metaltype<<endl;
}
g.close();

}