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>
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:
- Top down approach
- 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
◆ main()
Main function.
- Returns
- 0 on exit
91 {
93 return 0;
94}
static void test()
Test implementations.
Definition coin_change_topdown.cpp:74
◆ 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
48 {
49 if (n == 0) {
50 return 0;
51 }
54 }
55 int ans = INT_MAX;
56 for (int i = 0; i < t; i++) {
57 if (n - coins[i] >= 0) {
58
59 int sub =
mincoins(n - coins[i], coins, t,
dp);
61 }
62 }
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
for std::vector
Definition partition_problem.cpp:39
◆ test()
Test implementations.
- Returns
- void
74 {
75
76 const int64_t n1 = 15;
77 const int8_t t1 = 3, a1 = 0;
81 fill(dp1.begin(), dp1.end(), a1);
82 assert(dynamic_programming::mincoins_topdown::mincoins(n1, arr1, t1, dp1) ==
83 3);
85}
std::string fill(char c, int n)
Definition decimal_to_roman_numeral.cpp:15