#include <stdio.h>

#define MAXWEIGHT 100

int n = 3;			/* The number of objects */
int c[10] = { 8, 6, 4 };	/* c[i] is the weight of the ith object */
int v[10] = { 16, 10, 7 };	/* v[i] is the value of the ith object */
int W = 10;			/* The maximum weight you can take */

void
fillSack ()
{
  int a[MAXWEIGHT];		/* a[i] holds the maximum value that can be obtained
				   using at most i weight */
  int lastAdded[MAXWEIGHT];	/* This array remembers which object were
				   added */
  int i, j;
  int aux;

  for (i = 0; i <= W; ++i)
    {
      a[i] = 0;
      lastAdded[i] = -1;
    }

  a[0] = 0;
  for (i = 1; i <= W; ++i)
    for (j = 0; j < n; ++j)
      if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j]))
	{
	  a[i] = a[i - c[j]] + v[j];
	  lastAdded[i] = j;
	}

  for (i = 0; i <= W; ++i)
    if (lastAdded[i] != -1)
      printf
	("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n",
	 i, a[i], lastAdded[i] + 1, v[lastAdded[i]], c[lastAdded[i]],
	 i - c[lastAdded[i]]);
    else
      printf ("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);

  printf ("---\n");

  aux = W;
  while ((aux > 0) && (lastAdded[aux] != -1))
    {
      printf ("Added object %d (%d$ %dKg). Space left: %d\n",
	      lastAdded[aux] + 1, v[lastAdded[aux]], c[lastAdded[aux]],
	      aux - c[lastAdded[aux]]);
      aux -= c[lastAdded[aux]];
    }

  printf ("Total value added: %d$\n", a[W]);
}

int
main (int argc, char *argv[])
{
  fill_sack ();
  return 0;
}