Problem:
For a given maximum weight and a given number of objects,each with their own value and weight,display the object number and percentage inserted in the bag,for the combination with the highest value
#include <conio.h>
#include <iostream>
#pragma warning (disable : 4996)
usingnamespace std;
class Greedy
{ int o[100],N,M;
float val[100],weight[100],x[100],Gr;
public:
void imput()
{
int i;
cout<<"Imput maximum weight and number of objects"<<endl;
cin>>M>>N;
for (i=0;i<N;++i)
{
o[i]=i;
cout<<"Imput value and weight of object"<<i+1<<endl;
cin>>val[i]>>weight[i];
}
}
void order()
{
int i,aux,check;
do
{check=0;
for(i=0;i<N-1;++i)
if(val[o[i]]/weight[o[i]]<val[o[i+1]]/weight[o[i+1]])
{aux=o[i];
o[i]=o[i+1];
o[i+1]=aux;
check=1;
}
}
while(check);
}
void solve()
{
int i;
for(i=0,Gr=0;i<N-1;i++)
{if(Gr<weight[o[i]])
x[o[i]]=1;
Gr=Gr+weight[o[i]];
if(Gr>weight[o[i]])
x[o[i]]=weight[o[i]]/(Gr-weight[o[i]]);
Gr+=weight[o[i]];
if(Gr==M)
x[o[i]]=0;
}
}
void output()
{ int i;
for(i=0;i<N-1;i++)
if(x[i])
cout<<i+1<<":"<<x[i]*100<<"%"<<endl;
}
};
void main()
{Greedy g;
g.imput();
g.order();
g.solve();
g.output();
_getch();
}
When i run the code and insert the values,the output is very strange,and im not sure what to make of it.Ex:
For max weight 10 and 4 objects,defined with
values 3 4 4 3
weight 6 6 7 9
I get the following output:
1:23.0769%
2:58.3333%
3:100%
4:23.6842%
What I want to get:
1:0%
2:100%
3:57.14%
4:0%
There are some values for which i get the correct output but most of them are wrong.
#include <conio.h>
#include <iostream>
#pragma warning (disable : 4996)
usingnamespace std;
class Greedy
{ int o[100],N,M;
float val[100],weight[100],x[100],Gr;
public:
void imput()
{
int i;
cout<<"Imput maximum weight and number of objects"<<endl;
cin>>M>>N;
for (i=0;i<N;++i)
{
o[i]=i;
cout<<"Imput value and weight of object"<<i+1<<endl;
cin>>val[i]>>weight[i];
}
}
void order()
{
int i,aux,check;
do
{check=0;
for(i=0;i<N-1;++i)
if(val[o[i]]/weight[o[i]]<val[o[i+1]]/weight[o[i+1]])
{aux=o[i];
o[i]=o[i+1];
o[i+1]=aux;
check=1;
}
}
while(check);
}
void solve()
{
int i;
for(i=0,Gr=0;i<N;i++)
if((Gr+weight[o[i]])>M)// If the weight I have in the bag(GR)+the weight of the next object[weight[o[i]] is higher than the max weight(M)
{ //the else gives x the value 1 and increases the weight in the bag(Gr)
if(Gr<M) //Checks if the bag still has space left in it
{
x[o[i]]=(M-Gr)/weight[o[i]];//Calculates how much of the object can be inserted in the bag(from 0.000001 to 0.999999),from the proportion of the
//space left in the bag and the weight of the object and then increase Gr with that weight with the weight of the object*x[o[i]]
Gr=Gr+(weight[o[i]]*x[o[i]]);
}
}
else
{
x[o[i]]=1;
Gr=Gr+weight[o[i]];
if(Gr==M)
x[o[i]]=0;
}
}
void output()
{ int i;
for(i=0;i<N;i++)
if(x[i])
cout<<i+1<<":"<<x[i]*100<<"%"<<endl;
}
};
void main()
{Greedy g;
g.imput();
g.order();
g.solve();
g.output();
_getch();
}
The output im getting now is closer to what i want but still not there:
This is for the same imput I listed in the first post.
indentation
<nolyc> indentation is optional whitespace. see also: !vowel
vowel
<nolyc> vwls r bt s sfl s whtspc, spclly n vrbl nms. s ls: !ndnttn
> Also for imput max weight 10 and 2 objects ,both objects defined with value 5 and weight 5 i get
execute step by step through a debugger.
observe line 55.