[go: up one dir, main page]
Scribd
Upload
10 views3 pages

ADA14

The document discusses an algorithm for solving the coin change problem using dynamic programming. It describes the steps of the algorithm, provides C++ code to implement it, and gives an example output. The algorithm uses a bottom-up dynamic programming approach to find the minimum number of coins needed to make a given amount using coins in a list.

Uploaded by

MS Gauhar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
10 views3 pages

ADA14

The document discusses an algorithm for solving the coin change problem using dynamic programming. It describes the steps of the algorithm, provides C++ code to implement it, and gives an example output. The algorithm uses a bottom-up dynamic programming approach to find the minimum number of coins needed to make a given amount using coins in a list.

Uploaded by

MS Gauhar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

FACULTY OF

TECHNOLOGY
Information

Experiment 14

67
MD SARFUZZAMAN GAUHAR[92201704016] 4ED1( Page
FACULTY OF
TECHNOLOGY
Information

14 Write a program for coin change problem using dynamic programming

Algorithm:

Step 1: Define a function minCoins(amount, coins) that íetuíns the minimum numbeí of

coins needed to make amount using the coins in the list coins.

Step 2: Cíeate a list dp of length amount + 1, to stoíe the solutions of subpíoblems. Initialize

dp[0] to zeío, as no coins aíe needed to make zeío, and the íest of dp to infinity, as we

don’t know the solutions yet.

Step 3: Loop fíom i = 1 to i = amount:

o Loop thíough each coin c in coins:


 If c is less than oí equal to i, update dp[i] to the minimum of dp[i]
and 1 + dp[i - c], wheíe 1 íepíesents the coin c used in the solution.

Step 4: Retuín dp[amount] as the final answeí.

Code:

#include<iostream>
using namespace std;

int minCoins(int Coins[], int m, int v) {


if (v == 0) return 0;
int res = INT_MAX;
for (int i = 0; i < m; i++) {
if (Coins[i] <= v) {
int sub_res = minCoins(Coins, m, v -
Coins[i]);
if (sub_res != INT_MAX && sub_res + 1 <
res) {
res = sub_res + 1;
}

68
MD SARFUZZAMAN GAUHAR[92201704016] 4ED1( Page
FACULTY OF
TECHNOLOGY
Information

}
}
return res;
}

int main() {
int coins[] = {1, 2, 4, 5};
int m = sizeof(coins) / sizeof(coins[0]);
int v = 17;
cout << "Minimum coins required is: " <<
minCoins(coins, m, v);
return 0;
}

OUTPUT
Minimum Coins required is: 4

Time Complexity:
Best case:
Worst case:
Average case:

69
MD SARFUZZAMAN GAUHAR[92201704016] 4ED1( Page

You might also like