Design and Analysis of Algorithms - 10

by

Implement Program for “Making Change” using Dynamic Programming.

 

Code:


#include<stdlib.h>

 

struct change_entry

{

    unsigned int count;

    int coin;

    struct change_entry *prev;

};

typedef struct change_entry change_entry;

 

unsigned int make_change(const unsigned int *coins, size_t len, unsigned int value,

        unsigned int **solution)

{

    unsigned int i, j;

    change_entry **table;

    unsigned int result;

   

    table = malloc((len + 1) * sizeof(change_entry *));

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

    {

        table[i] = malloc((value + 1) * sizeof(change_entry));

    }

 

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

    {

        for (j = 0; j <= value; j++)

        {

            if (i == 0)

            {

               

                table[i][j].count = j;

                table[i][j].coin = -1;

                table[i][j].prev = NULL;

            }

            else if (j == 0)

            {

                table[i][j].count = 0;

                table[i][j].coin = -1;

                table[i][j].prev = NULL;

            }

            else if (coins[i - 1] == j)

            {

                table[i][j].count = 1;

                table[i][j].coin = i - 1;

                table[i][j].prev = NULL;

            }

            else if (coins[i - 1] > j)

            {

                table[i][j].count = table[i - 1][j].count;

                table[i][j].coin = -1;

                table[i][j].prev = &table[i - 1][j];

            }

            else

            {

                if (table[i - 1][j].count < table[i][j - coins[i - 1]].count + 1)

                {

                    table[i][j].count = table[i - 1][j].count;

                    table[i][j].coin = -1;

                    table[i][j].prev = &table[i - 1][j];

                }

                else

                {

                    table[i][j].count = table[i][j - coins[i - 1]].count + 1;

                    table[i][j].coin = i - 1;

                    table[i][j].prev = &table[i][j - coins[i - 1]];

                }

            }

        }

    }

    result = table[len][value].count;

    *solution = calloc(len, sizeof(unsigned int));

    if (*solution)

    {

        change_entry *head;

        for (head = &table[len][value];

                head != NULL;

                head = head->prev)

                {

            if (head->coin != -1)

            {

                (*solution)[head->coin]++;

            }

        }

    }

    else

    {

        result = 0;

    }

    

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

    {

        free(table[i]);

    }

    free(table);

 

    return result;

}

 

int main(void)

{

    unsigned int coins[] = {1, 2, 5, 10, 20, 50, 100};

    const size_t len = sizeof(coins) / sizeof(coins[0]);

    const unsigned int value = 480;

    unsigned int *solution;

    unsigned int result = make_change(coins, len, value, &solution);

    unsigned int i;

    printf("Number of coins: %u\n", result);

    printf("Coins used:\n");

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

    {

        if (solution[i] > 0)

        {

            printf("%u x %u\n", solution[i], coins[i]);

        }

    }

    free(solution);

    return 0;

}


Output:


 

 

 




Conclusion:

In this Practical, I understand to Implement program for “Making Change” using Dynamic Programming.

Comments

Post a Comment

Popular posts from this blog

Computer Architecture and Organization - 4

by
Image
Aim:  To implement various 4-bit arithmetic Micro-operations           using arithmetic unit.   Theory Arithmetic micro operation of the form L:   R A  ( R A + R B ) refers to two data items contained in R A and R B input to a parallel adder with the result being stored back in R A (Fig.). Loading      of the result in R A is subject to the availability   of the control   signal designated as L   (that   is   load control of R A ) . Note that adder being a combinational logic, the adder output is available after a delay of the associated combinational circuit. Input to adder may be also controlled by providing AND word gates on the data paths from R A and R B to the adder under the control signal C (Fig.). the control signals `C' and 2's complement are at logic `0' for add operation.   The subtract micro operation L:   R A  ( R A - R B ) in 2's comp...
Read more

Design and Analysis of Algorithms - 2

by
Image
Implement functions to print n th Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart. Code:   #include<stdio.h>   int count_ite=0; int count_rec=0; void febo_ite(int ); int febo_rec(int );   int main() {     int n,ans;     printf("Enter position of number: ");     scanf("%d",&n);     febo_ite(n);     ans=febo_rec(n);     printf("Using Recursion: %d th number is = %d\n",n,ans);     printf("No of Steps= %d\n\n",count_rec); }   void febo_ite(int n) {     count_ite++;     int next,i, first=0,second=1;     count_ite++;     if(n==0)     {         count_ite++;  ...
Read more

Design and Analysis of Algorithms - 6

by
Image
Implement program for randomized version of quick sort and compare its performance with normal version of quick sort using steps count on various number of inputs.   Code: #include<stdio.h> #include<stdlib.h> #include<time.h>   int count=0; int r_count=0; void quick_sort(int a[],int start,int n) {     int i,j,pivot,temp;     count++;     if(start<n)         {             count++;             pivot=start;             count++;             i=start;             count++;             j=n;     ...
Read more

Design and Analysis of Algorithms - 1

by
Image
Implement a function for each of following problems and count the  number of steps executed/Time taken by each function on various  inputs and write complexity of each function. Also draw a  comparative chart. In each of the following function N will be passed  by user.                     1. To calculate sum of 1 to N number using loop.                     2. To calculate sum of 1 to N number using equation.                     3. To calculate sum of 1 to N numbers using recursion. Code:   #include <stdio.h> int count_loop=0; int count_rec=0; int count_eq=0;   int sum_loop(int n) {     int i,sum=0;     count_loop++;     for(i=1;i<=n;i++)     {         count_loop++; ...
Read more

Artificial Intelligence - 7

by
Image
  AIM: Write a program to build Multi-layer Perceptron to implement any Boolean functions as mentioned below without using any python packages. AND, OR, XOR, XNOR, NOR, NAND, NOT x1, NOT x2, NULL, IDENTITY, INHIBITION ( 𝑥 1 ∧ ¬ 𝑥 2), INHIBITION ( 𝑥 2 ∧ ¬ 𝑥 1), TRANSFER x1, TRANSFER x2, IMPLICATION ( 𝑥 1 ∨ ¬ 𝑥 2), IMPLICATION ( 𝑥 2 ∨ ¬ 𝑥 1)   Program: class  perceptronNeuron:      def   __init__ ( self ,  x ,  w ,  w0 ):         l = [ww  for  ww  in  x]         l.insert( 0 ,  1 )          self .x = l          self .y =  0         l = [ww  for  ww  in  w]         l.insert( 0 ,...
Read more