1  
   2  #include <stdio.h>
   3  
   4  int n = 5; /* The number of objects */
   5  int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what
   6  				YOU PAY to take the object */
   7  int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.
   8  				what YOU GET for taking the object */
   9  int W = 15; /* The maximum weight you can take */
  10  
  11  void simple_fill() {
  12  	int cur_w;
  13  	float tot_v;
  14  	int i, maxi;
  15  	int used[10];
  16  
  17  	for (i = 0; i < n; ++i)
  18  		used[i] = 0; /* I have not used the ith object yet */
  19  
  20  	cur_w = W;
  21  	while (cur_w > 0) { /* while there's still room*/
  22  		/* Find the best object */
  23  		maxi = -1;
  24  		for (i = 0; i < n; ++i)
  25  			if ((used[i] == 0) &&
  26  				((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
  27  				maxi = i;
  28  
  29  		used[maxi] = 1; /* mark the maxi-th object as used */
  30  		cur_w -= c[maxi]; /* with the object in the bag, I can carry less */
  31  		tot_v += v[maxi];
  32  		if (cur_w >= 0)
  33  			printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
  34  		else {
  35  			printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
  36  			tot_v -= v[maxi];
  37  			tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
  38  		}
  39  	}
  40  
  41  	printf("Filled the bag with objects worth %.2f$.\n", tot_v);
  42  }
  43  
  44  int main(int argc, char *argv[]) {
  45  	simple_fill();
  46  
  47  	return 0;
  48  }