South East University
CSE 376(Advance Algorithms)
Lab 7 Manual
(Implementation of DP Coin Changing Algorithms)
Course instructor
Dr. Md. Tauhid Bin Iqbal
Assistant Professor
Department of Computer Science & Engineering
Lab Task:In this lab, you will explore the concept of Dynamic Programming (DP),
a powerful technique used to solve optimization problems where the solution to a
larger problem can be constructed by combining the solutions of its smaller
subproblems. You will implement solutions for 2 classic dynamic programming
problems of Coin Changing problem
Tasks:
Coin Change Problem:
Problem Statement:
You are given a set of coin denominations and a target amount. The goal is to
determine the minimum number of coins required to make the target amount. You
can use each coin denomination any number of times.
2nd problem Statement:
You are given a set of coin denominations and a target amount. The goal is to
determine the maximum number of way of giving coins required to make the target
amount. You can use each coin denomination any number of times.
Lab Implementation Instructions:
Understand the Theory: Review the theory of Dynamic Algorithm and how they apply
to the problems.
Implement the Solutions: Code the solutions for the 2 Dynamic problems (Coin
Change, 0/1 Knapsack)
Test the Algorithms: Test your implementations with different input values to check
the correctness of the algorithms.
Coin change Algorithm to find the
Minimum Numbers of the coin
Why not solving the coin change problem with only the Greedy Method doesn’t it
give the optimal solution all the time??
Problem Statement:
Given coin denominations {1, 3, 4} and a target amount 6, find the minimum number
of coins needed to make the target amount.
Greedy Approach:
In the greedy approach, we always choose the largest denomination that is less than or
equal to the remaining amount. This is done in a greedy manner, hoping that it will
lead to an optimal solution.
Greedy Solution Steps:
Start with amount 6.
Choose the largest coin less than or equal to 6, which is 4.
Remaining amount: 6 - 4 = 2.
Choose the largest coin less than or equal to 2, which is 1.
Remaining amount: 2 - 1 = 1.
Choose the largest coin less than or equal to 1, which is 1.
Remaining amount: 1 - 1 = 0.
Thus, using the greedy approach, the solution would be:
Coins used: {4, 1, 1} for Greedy Approch
Total coins: 3.
Optimal Solution (Dynamic Programming):
Using dynamic programming, we can find the optimal solution by building up the
solution from smaller subproblems. Here's how we would do it:
DP Table Setup: We create a DP table to store the minimum number of coins required
to make each amount from 0 to 6.
DP Recurrence:
dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1) for each coin denomination.
DP Solution:
For amount 6, the minimum number of coins is 2, and the solution is:
Coins used: {3, 3}.
Thus, the optimal solution is to use two coins of denomination 3.
Comparison:
Greedy approach: {4, 1, 1} (3 coins).
Optimal solution: {3, 3} (2 coins).
We havc coins of {1,2,3} and we have to return the amount of 5
Available Coins Total Total Total Total Total Amount Total Amount = 5
Amount Amount Amount = 2 Amount = 3 = 4
=0 =1
0 (no coins) 0 inf inf inf inf inf
1 (coin 1) 0 1 2 3 4 5
2 (coin 1, 2) 0 1 1 2 3 3
3 (coin 1, 2, 3) 0 1 1 1 2 2
dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1)
i = 3 → current coin = 4
j = 5 → target amount = 5
Here, dp[i-1][j]= 3
or
dp[i][j - coins[i]] + 1
j - coins[i] = 5 - 3 = 2
So we look at dp[3][2] + 1.
So, we find dp[3][2] = 1
dp[3][1] + 1
= 1 + 1 = 2.
min(dp[i-1][j], dp[i][j - coins[i]] + 1)= min (3,2)=2
PseudoCode:
function coinChange(coins[], amount):
// Initialize a DP array with a large number (infinity)
dp = array of size (amount + 1) // Initialize the array for storing minimum coins
needed for each amount
dp[0] = 0 // Base case: 0 coins are required to make amount 0
// Fill the DP table using bottom-up approach
for i = 1 to amount:
dp[i] = infinity // Initialize with a large number
// Loop through all amounts from 1 to 'amount'
for i = 1 to amount:
// Try each coin
for each coin in coins:
if i >= coin: // If the current amount is greater than or equal to the coin's value
dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1)
// Minimize the number of coins
else i < coin //coin cannot be used
dp[i][j] = dp[i-1][j]
// If dp[amount] is still infinity, it means it's not possible to make the amount with given coins
if dp[amount] == infinity:
return -1 // Return -1 if it's not possible to make the amount
else:
return dp[amount] // Return the minimum number of coins needed
Coin change Algorithm to find the
Maximum ways of the coin change
Pseudocode
function countWays(coins, n, target):
Coins = list of coin values
n = number of coins
target = amount we want to make
dp[j] = number of ways to make amount j
create array dp[0..target] initialized with 0
dp[0] = 1 # base case: 1 way to make amount 0 (use no coins)
for i from 1 to n:
for j from coins[i] to target:
if coin> amount
dp[i][j] = dp[i-1][j]
else coin<=amount
dp[j] = dp[j] + dp[j - coins[i]]
return dp[target]
Show all the ways that the coins can be returned .
