1  
   2  #include <stdio.h>
   3  
   4  #define MAXWEIGHT 100
   5  
   6  int n = 3; /* The number of objects */
   7  int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
   8  				YOU PAY to take the object */
   9  int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
  10  				what YOU GET for taking the object */
  11  int W = 10; /* The maximum weight you can take */ 
  12  
  13  void fill_sack() {
  14  	int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
  15  				using at most i weight */
  16  	int last_added[MAXWEIGHT]; /* I use this to calculate which object were
  17  					added */
  18  	int i, j;
  19  	int aux;
  20  
  21  	for (i = 0; i <= W; ++i) {
  22  		a[i] = 0;
  23  		last_added[i] = -1;
  24  	}
  25  
  26  	a[0] = 0;
  27  	for (i = 1; i <= W; ++i)
  28  		for (j = 0; j < n; ++j)
  29  			if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
  30  				a[i] = a[i - c[j]] + v[j];
  31  				last_added[i] = j;
  32  			}
  33  
  34  	for (i = 0; i <= W; ++i)
  35  		if (last_added[i] != -1)
  36  			printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);
  37  		else
  38  			printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);
  39  
  40  	printf("---\n");
  41  
  42  	aux = W;
  43  	while ((aux > 0) && (last_added[aux] != -1)) {
  44  		printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
  45  		aux -= c[last_added[aux]];
  46  	}
  47  
  48  	printf("Total value added: %d$\n", a[W]);
  49  }
  50  
  51  int main(int argc, char *argv[]) {
  52  	fill_sack();
  53  
  54  	return 0;
  55  }