Question

Let d1> d2 >… dm be the set of coin denominations and n is the amount of money in cents. The goal is to find the least number of coins of a given n and denominations, dm. Based on Brute Force design strategy, show your solution to find the goal if d1 = 25 cents, d2 = 15 cents and d3 = 1 cent and n = 31

Answer 1

Answer:

// A Naive recursive C++ program to find minimum of coins

// to make a given change V

#include<bits/stdc++.h>

using namespace std;

// m is size of coins array (number of different coins)

int minCoins(int coins[], int m, int V)

{

// base case

if (V == 0) return 0;

// Initialize result

int res = INT_MAX;

// Try every coin that has smaller value than V

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

{

if (coins[i] <= V)

{

int sub_res = minCoins(coins, m, V-coins[i]);

// Check for INT_MAX to avoid overflow and see if

// result can minimized

if (sub_res != INT_MAX && sub_res + 1 < res)

res = sub_res + 1;

}

}

return res;

}

// Driver program to test above function

int main()

{

int coins[] = {9, 6, 5, 1};

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

int V = 11;

cout << "Minimum coins required is "

<< minCoins(coins, m, V);

return 0;

}