coin_change_topdown.cpp File Reference

Minimum coins change problem is a problem used to find the minimum number of coins required to completely reach a target amount. More...

#include <cassert>
#include <climits>
#include <iostream>
#include <vector>

Include dependency graph for coin_change_topdown.cpp:

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	mincoins_topdown
	Functions for minimum coin exchange problem.

Functions
template<typename T >
int64_t	dynamic_programming::mincoins_topdown::mincoins (const T &n, const std::vector< T > &coins, const int16_t &t, std::vector< T > dp)
	This implementation is for finding minimum number of coins .
static void	test ()
	Test implementations.
int	main ()
	Main function.

Detailed Description

Minimum coins change problem is a problem used to find the minimum number of coins required to completely reach a target amount.

This problem can be solved using 2 methods:

1. Top down approach
2. Bottom up appraoch Top down approach involves a vector with all elements initialised to 0. It is based on optimal substructure and overlapping subproblems. Overall time complexity of coin change problem is O(n*t) For example: example 1:- Coins: {1,7,10} Target:15 Therfore minimum number of coins required = 3 of denomination 1,7 and 7.

   Author

   Divyansh Kushwaha

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // execute the test
    return 0;
}

Here is the call graph for this function:

mincoins()

template<typename T >

int64_t dynamic_programming::mincoins_topdown::mincoins	(	const T &	n,
		const std::vector< T > &	coins,
		const int16_t &	t,
		std::vector< T >	dp )

This implementation is for finding minimum number of coins .

Parameters

T	template-type to use any kind of value
n	amount to be reached
coins	vector of coins
t	deontes the number of coins
dp	initilised to 0

Returns

minimum number of coins

                                  {
    if (n == 0) {
        return 0;
    }
    if (dp[n] != 0) {
        return dp[n];
    }
    int ans = INT_MAX;  // variable to store min coins
    for (int i = 0; i < t; i++) {
        if (n - coins[i] >= 0) {  // if after subtracting the current
                                  // denomination is it greater than 0 or not
            int sub = mincoins(n - coins[i], coins, t, dp);
            ans = std::min(ans, sub + 1);
        }
    }
    dp[n] = ans;
    return dp[n];  // returns minimum number of coins
}

Here is the call graph for this function:

test()

static void test ( )

static

Test implementations.

Returns

void

                   {
    // example 1: number of coins=3 and minimum coins required=3(7,7,1)
    const int64_t n1 = 15;
    const int8_t t1 = 3, a1 = 0;
    std::cout << "\nTest 1...";
    std::vector<int64_t> arr1{1, 7, 10};
    std::vector<int64_t> dp1(n1 + 1);
    fill(dp1.begin(), dp1.end(), a1);
    assert(dynamic_programming::mincoins_topdown::mincoins(n1, arr1, t1, dp1) ==
           3);
    std::cout << "Passed\n";
}

Here is the call graph for this function: