Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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
91 {
92 test(); // execute the test
93 return 0;
94}
static void test()
Test implementations.
Definition coin_change_topdown.cpp:74
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
Ttemplate-type to use any kind of value
namount to be reached
coinsvector of coins
tdeontes the number of coins
dpinitilised to 0
Returns
minimum number of coins
48 {
49 if (n == 0) {
50 return 0;
51 }
52 if (dp[n] != 0) {
53 return dp[n];
54 }
55 int ans = INT_MAX; // variable to store min coins
56 for (int i = 0; i < t; i++) {
57 if (n - coins[i] >= 0) { // if after subtracting the current
58 // denomination is it greater than 0 or not
59 int sub = mincoins(n - coins[i], coins, t, dp);
60 ans = std::min(ans, sub + 1);
61 }
62 }
63 dp[n] = ans;
64 return dp[n]; // returns minimum number of coins
65}
int64_t 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 .
Definition coin_change_topdown.cpp:47
T min(T... args)
for std::vector
Definition partition_problem.cpp:39
Here is the call graph for this function:

◆ test()

static void test ( )
static

Test implementations.

Returns
void
74 {
75 // example 1: number of coins=3 and minimum coins required=3(7,7,1)
76 const int64_t n1 = 15;
77 const int8_t t1 = 3, a1 = 0;
78 std::cout << "\nTest 1...";
79 std::vector<int64_t> arr1{1, 7, 10};
80 std::vector<int64_t> dp1(n1 + 1);
81 fill(dp1.begin(), dp1.end(), a1);
82 assert(dynamic_programming::mincoins_topdown::mincoins(n1, arr1, t1, dp1) ==
83 3);
84 std::cout << "Passed\n";
85}
std::string fill(char c, int n)
Definition decimal_to_roman_numeral.cpp:15
Here is the call graph for this function: