mincoin.c

/*
    Name: Mincoin.c
    Copyright:
    Author: Mr.Kindle
    Date: 22-12-22 11:21
    Description: This code the minimum number of coin required to make a target sum. e.g if we have 4 coins of
     1,3,5,7 and the target sum is 10. then minimum 2 coin will be required to make this sum.
     If target sum is not possible using these coins then it print that the sum cannot be obtained
     using these coins.It also print all the coins which required to make the target sum.
*/



#include <malloc.h>
#include <stdio.h>
#include<stdlib.h>
#define INFINITY 99

int min(int,int);
void print_coins(int *dpmat, int col, int * coin);

 int n, t_sum;//taking both global so that all function can access it.

int main(void) {


  int i, j,col;
  int *coin;
  int * dpmat;
  int * r_coin;//store the coins required for target sum
  int result;
  char reply;

  printf("Enter total number of coins of different denomination\n");
  scanf("%d", &n);
  coin = calloc(n, sizeof(int));

  printf("\nPlease enter all different denomination of coins : ");
  for (i = 0; i < n; i++) {
    printf("\nEnter coin %d:  ", i+1 );
    scanf("%d", &coin[i]);
  }
  printf("\nEnter target sum:  ");
  scanf("%d", &t_sum);

dpmat = calloc(n * (t_sum + 1), sizeof(int));
col = t_sum + 1;//This column is used to access the elements of the dynamically allocated dpmatrix.This col is
//total width of the column of dpmat not the index of the last column.


  for (i = 0; i < n; i++) {
    for (j = 0; j <= t_sum; j++) {
/*for first row of dpmatrix*/
     if (i == 0)//if value of coin greater than the target at column j
        {
            if(j%coin[i] == 0)
                dpmat[i*col + j] = j/coin[i];
            else
                dpmat[i*col +j] = INFINITY;
        }
      else if(coin[i] > j)
        {
            dpmat[i*col +j] = dpmat[(i-1)*col + j];
        }
    else
        dpmat[i*col +j] = min(dpmat[(i-1)*col + j],1+dpmat[i*col + (j - coin[i])]);
    }
  }



  /*The last element of the dpmatrix is the answer hence printing the last element*/
  /*Last element is the cross section of the last row and the last column*/
  result = dpmat[(n - 1)* col + (t_sum)];
  if(result == INFINITY)
    {
        printf("\nThis sum cannot be obtained using these coins: ");
        exit(1);
    }
    else
  printf("\nMinumum number of coin required is = %d",result);
  /*Now calling a function which will print all the required coins*/
    print_coins(dpmat,col,coin);//sending col as argument because dpmat is dynamically allocated and hence in order
    //to access it's element its width is required which is col.



    printf("\nHey! do you want to print the DP matrix for this probem? \n");
    printf("Press 'Y' for yes & 'N' for no: ");
    scanf(" %c",&reply);
    if(reply == 'y' || reply == 'Y')
        {
            printf("\n\nFollowing is your dpmatrix: \n\n");
            printf("\n\n");
            printf("Sum->");

            for (i = 0; i <= t_sum; i++)

                printf("%2d ",i);

            printf("\n");
            printf("Coin \n");

            for (i = 0; i < n; i++) {
                printf(" %d   ",coin[i]);
                for (j = 0; j <= t_sum; j++) {
                    printf("%2d ", dpmat[i * col +j]);
                }
                 printf("\n");
            }
            printf("\n\n*******NOTE*******");
            printf("\n99 means infinite, It shows that this sum cannot be made using this or these coins> .");
        }
 free(coin);


  free(dpmat);
  return 0;
}//main

int min(int a, int b)
    {
        if (a<=b)
            return a;
        else
            return b;
    }//end of min

void print_coins(int *dpmat, int col, int * coin)
    {
         /*Now all code following are in order to print all the required coins*/
  /*Its complicated but what can I do guys.*/
    int pointer,i,k=0,sum = t_sum; //we cannot change value of t_sum because then 'col = t_sum + 1' will be changed
        //and if col changed then we cannot access dpmat's element because it is dynamically allocated

    int *r_coin;
        /*This pointer will initially point to the last element of dpmat which is result also*/
        pointer = dpmat[(n - 1)* col + (t_sum)];//last element of dpmat which is result
        int column = t_sum ;//currently this column is index of the last column of dpmat
        int row = n-2;//first time the pointer will be in last row hence we will start comparison from 2nd lastrow
        //please understand the difference between 'column' and 'col' declared above.
        /*The required coin may be in large numbers so making r_coin a big array*/
        r_coin = calloc(100, sizeof(int));


  while(sum)//untill sum != 0
    {

        /*keep moving the pointer in above direction in same  column until we get different values*/
        for(i=row;i>=0;i--)
            {
                if(pointer == dpmat[i*col + column])
                    {
                        pointer = dpmat[i*col + column];

                    }
                else
                    break;
            }

            /*coin[i+1] is the coin correspondig to the row in which currently the pointer is.*/
            //we store this coin in R_coin array
            r_coin[k++] = coin[i+1];
            //since we got first coin hence will reduce it from the target sum which is sum now.
            sum = sum - coin[i+1];
            //the row in which the pointer is now will be compared with previous row hence now
            row = i; //since i+1 is the row containing pointer hence i will be the previous row
            //remaining sum will be new column for the pointer now
            column = sum;//remaining sum
            /*pointer will point to the last row and current column.Current column is remaining sum*/
            pointer = dpmat[(i+1)* col + column];
        /*repeat the same process untill we get sum == 0*/
    }
    printf("\n\nThe Required coins are following:  \n\n");
    for(i=0;i<k;i++)//'k' is also working as a counter.
        printf("%d ",r_coin[i]);

    free(r_coin);

    }