Greedy implementation not working as intended

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <conio.h>
#include <iostream>
#pragma warning (disable : 4996)
using namespace 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.
It would be a lot easier to spot if you learn to indent your code.
In fact, you probably shouldn't bother, simple tell your IDE to do it.

lines 43 and 46 are executed always.
┬┐may you explain the conditions in line 41 and 44?
Changed a few things in the code and added a few comments:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <conio.h>
#include <iostream>
#pragma warning (disable : 4996)
using namespace 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.

1:-1.07374e+010%
2:100%
3:57.1429%
4:-1.07374e+010%

1: and 4: should be 0
Also for imput max weight 10 and 2 objects ,both objects defined with value 5 and weight 5 i get
1:100%

I should get:

1:100%
2:100%
Last edited on
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.
Topic archived. No new replies allowed.