Question

Recall the coin changing problem: given coins of denomination d_i zonks, where 1 = d₁ < d₂ < ··· < d_k, and infinitely many coins of each denomination, find the minimum number of coins needed to make exact change for n zonks.

Here we ask a different problem. Each coin has a weight, the weight of each coin with denomination d_i being w_i > 0. We want to make exact change while minimizing the total weight of the coins used.

(a) Suppose the denominations are 1, 5, 10, 25, 50 with respective weights 1, 2, 2, 6, 12. Give the optimal solution for n = 60.

(b) Describe in detail a dynamic programming algorithm to make change for n zonks such that the total weight of coins used is minimized, and give its asymptotic worst-case running time.

Answer 1

#include<stdio.h>

int count( int S[], int m, int n )

{

    int i, j, x, y;

    // We need n+1 rows as the table is consturcted in bottom up manner using

    // the base case 0 value case (n = 0)

    int table[n+1][m];

    

    // Fill the enteries for 0 value case (n = 0)

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

        table[0][i] = 1;

    // Fill rest of the table enteries in bottom up manner

    for (i = 1; i < n+1; i++)

    {

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

        {

            // Count of solutions including S[j]

            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

            // Count of solutions excluding S[j]

            y = (j >= 1)? table[i][j-1]: 0;

            // total count

            table[i][j] = x + y;

        }

    }

    return table[n][m-1];

}

// Driver program to test above function

int main()

{

    int arr[] = {1, 2, 3};

    int m = sizeof(arr)/sizeof(arr[0]);

    int n = 4;

    printf(" %d ", count(arr, m, n));

    return 0;

}