Scribd
Upload
3 views2 pages

Handout - Dynamic Programming - Tabulation

The document contains a C++ program that implements a coin change algorithm to determine the minimum number of coins needed to make a specified amount using given coin denominations. It uses dynamic programming to build a solution and outputs the minimum coins required along with the specific coins used. In the provided example, for an amount of 11 with coins of denominations 1, 2, and 5, the program finds that 3 coins are needed, specifically two 5s and one 1.

Uploaded by

whoarey196
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
3 views2 pages

Handout - Dynamic Programming - Tabulation

The document contains a C++ program that implements a coin change algorithm to determine the minimum number of coins needed to make a specified amount using given coin denominations. It uses dynamic programming to build a solution and outputs the minimum coins required along with the specific coins used. In the provided example, for an amount of 11 with coins of denominations 1, 2, and 5, the program finds that 3 coins are needed, specifically two 5s and one 1.

Uploaded by

whoarey196
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

#include <bits/stdc++.

h>

using namespace std;

void coinChangeWithCoins(vector<int>& coins, int amount) {

vector<int> dp(amount + 1, INT_MAX);

vector<int> parent(amount + 1, -1);

dp[0] = 0;

for (int i = 1; i <= amount; i++) {

for (int coin : coins) {

if (coin <= i && dp[i - coin] != INT_MAX) {

if (dp[i] > dp[i - coin] + 1) {

dp[i] = dp[i - coin] + 1;

parent[i] = coin; // store coin used

if (dp[amount] == INT_MAX) {

cout << "No solution possible\n";

return;

cout << "Minimum coins required: " << dp[amount] << endl;

cout << "Coins used: ";

int curr = amount;


while (curr > 0) {

cout << parent[curr] << " ";

curr -= parent[curr];

cout << endl;

int main() {

vector<int> coins = {1, 2, 5};

int amount = 11;

coinChangeWithCoins(coins, amount);

return 0;

Output:

Minimum coins required: 3

Coins used: 1 5 5

You might also like