void input (int *values) {
   int i,j;
   for (i=0; i<5; i++) {
      printf ("Value for coin %d: ", i+1);
      scanf ("%d", &values[i]);
      for (j=i-1; j>=0; j--) {
	 if (values[j] > values[j+1]) {
	    int temp = values[j];
	    values[j]=values[j+1];
	    values[j+1]=temp;
	    }
	 }
      }
   }

void output (int coins, int *values, int *count) {
   int i;

   if (coins == 1000000) printf ("Can't make change for this amount.\n");
   else {
      printf ("You need ");
      for (i=0; i<5; i++) {
         if (i) printf ("         ");
         printf ("%d coins of value %d\n", count[i],values[i]);
         }
      }
   }

int addup (int *count) {
   int i,num;
   num = 0;
   for (i=0; i<5; i++) {
      num += count[i];
      }
   return num;
   }

int solve (int total, int *values, int *count) {
/* uses total, values; sets count; return val is num coins */
   int i,j,numwith,numwithout;
   int newcount[5],newvalues[5];

   for (i=0;i<5;i++) count[i]=0;

   if (total == 0) return 0;

   for (i=0; i<5; i++) {
      if (values[i] > total) newvalues[i] = 0;
      else newvalues[i] = values[i];
      }

   if (addup(newvalues) == 0) return 1000000;

   for (i=0; i<5; i++) {
      if (newvalues[i]) {
         numwith = solve (total-newvalues[i], newvalues, count);
	 newvalues[i] = 0;
	 numwithout = solve (total, newvalues, newcount);
	 newvalues[i] = values[i];

	 if (numwith < numwithout) {
	    count[i]++;
	    return numwith+1;
	    }
	 else {
	    for (j=0; j<5; j++) count[j]=newcount[j];
	    return numwithout;
	    }
         }
      }
   }
	    

void main (void) {
   int values[5];
   int count[5];
   int total;
   int coins;

   input (values);
   printf ("How much change is needed?");
   scanf ("%d",&total);
   coins = solve (total,values,count);
   output (coins,values,count);
   }