Coin Change – Minimum Coins to Make Sum
Last Updated :
15 Nov, 2024
Given an array of coins[] of size n and a target value sum, where coins[i] represent the coins of different denominations. You have an infinite supply of each of the coins. The task is to find the minimum number of coins required to make the given value sum. If it’s not possible to make a change, return -1.
Examples:
Input: coins[] = [25, 10, 5], sum = 30
Output: 2
Explanation : Minimum 2 coins needed, 25 and 5
Input: coins[] = [9, 6, 5, 1], sum = 19
Output: 3
Explanation: 19 = 9 + 9 + 1
Input: coins[] = [5, 1], sum = 0
Output: 0
Explanation: For 0 sum, we do not need a coin
Input: coins[] = [4, 6, 2], sum = 5
Output: -1
Explanation: Not possible to make the given sum.
Using Recursion – O(n^sum) Time and O(sum) Space
This problem is a variation of the problem Coin Change Problem. Here instead of finding the total number of possible solutions, we need to find the solution with the minimum number of coins.
The idea is to find the minimum number of coins required to reach the target sum by trying each coin denomination in the coins[] array. Starting from the target sum, for each coin coins[i], we can either include it or exclude it. If we include it, we subtract its value from sum and recursively try to make the remaining amount with the same coin denominations. If we exclude it, we move to the next coin in the list.
Mathematically the recurrence relation will look like the following:
minCoins(i, sum, coins) = min(1 + minCoins(i, sum-coins[i], coins), minCoins(i+1, sum, coins))
Base cases:
- minCoins(i, sum, coins) = 0, if sum = 0.
- minCoins(i, sum, coins) = INTEGER MAX, if sum < 0 or i == size of coins.
C++
// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;
int minCoinsRecur(int i, int sum, vector<int> &coins) {
// base case
if (sum == 0) return 0;
if (sum <0 || i == coins.size()) return INT_MAX;
int take = INT_MAX;
// take a coin only if its value
// is greater than 0.
if (coins[i]>0) {
take = minCoinsRecur(i, sum-coins[i], coins);
if (take != INT_MAX) take++;
}
int noTake = minCoinsRecur(i+1, sum, coins);
return min(take, noTake);
}
int minCoins(vector<int> &coins, int sum) {
int ans = minCoinsRecur(0, sum, coins);
return ans!=INT_MAX?ans:-1;
}
int main() {
vector<int> coins = {9, 6, 5, 1};
int sum = 19;
cout << minCoins(coins, sum);
return 0;
}
// Java program to find minimum of coins
// to make a given change sum
import java.util.Arrays;
class GfG {
static int minCoinsRecur(int i, int sum, int[] coins) {
// base case
if (sum == 0) return 0;
if (sum < 0 || i == coins.length) return Integer.MAX_VALUE;
int take = Integer.MAX_VALUE;
// take a coin only if its value
// is greater than 0.
if (coins[i] > 0) {
take = minCoinsRecur(i, sum - coins[i], coins);
if (take != Integer.MAX_VALUE) take++;
}
int noTake = minCoinsRecur(i + 1, sum, coins);
return Math.min(take, noTake);
}
static int minCoins(int[] coins, int sum) {
int ans = minCoinsRecur(0, sum, coins);
return ans != Integer.MAX_VALUE ? ans : -1;
}
public static void main(String[] args) {
int[] coins = {9, 6, 5, 1};
int sum = 19;
System.out.println(minCoins(coins, sum));
}
}
# Python program to find minimum of coins
# to make a given change sum
def minCoinsRecur(i, sum, coins):
# base case
if sum == 0:
return 0
if sum < 0 or i == len(coins):
return float('inf')
take = float('inf')
# take a coin only if its value
# is greater than 0.
if coins[i] > 0:
take = minCoinsRecur(i, sum - coins[i], coins)
if take != float('inf'):
take += 1
noTake = minCoinsRecur(i + 1, sum, coins)
return min(take, noTake)
def minCoins(coins, sum):
ans = minCoinsRecur(0, sum, coins)
return ans if ans != float('inf') else -1
if __name__ == "__main__":
coins = [9, 6, 5, 1]
sum = 19
print(minCoins(coins, sum))
// C# program to find minimum of coins
// to make a given change sum
using System;
class GfG {
static int minCoinsRecur(int i, int sum, int[] coins) {
// base case
if (sum == 0) return 0;
if (sum < 0 || i == coins.Length) return int.MaxValue;
int take = int.MaxValue;
// take a coin only if its value
// is greater than 0.
if (coins[i] > 0) {
take = minCoinsRecur(i, sum - coins[i], coins);
if (take != int.MaxValue) take++;
}
int noTake = minCoinsRecur(i + 1, sum, coins);
return Math.Min(take, noTake);
}
static int minCoins(int[] coins, int sum) {
int ans = minCoinsRecur(0, sum, coins);
return ans != int.MaxValue ? ans : -1;
}
static void Main(string[] args) {
int[] coins = { 9, 6, 5, 1 };
int sum = 19;
Console.WriteLine(minCoins(coins, sum));
}
}
// JavaScript program to find minimum of coins
// to make a given change sum
function minCoinsRecur(i, sum, coins) {
// base case
if (sum === 0) return 0;
if (sum < 0 || i === coins.length) return Number.MAX_VALUE;
let take = Number.MAX_VALUE;
// take a coin only if its value
// is greater than 0.
if (coins[i] > 0) {
take = minCoinsRecur(i, sum - coins[i], coins);
if (take !== Number.MAX_VALUE) take++;
}
let noTake = minCoinsRecur(i + 1, sum, coins);
return Math.min(take, noTake);
}
function minCoins(coins, sum) {
let ans = minCoinsRecur(0, sum, coins);
return ans !== Number.MAX_VALUE ? ans : -1;
}
const coins = [9, 6, 5, 1];
const sum = 19;
console.log(minCoins(coins, sum));
Using Top-Down DP (Memoization) – O(n*sum) Time and O(n*sum) Space
If we notice carefully, we can observe that the above recursive solution holds the following two properties of Dynamic Programming:
1. Optimal Substructure:
Minimum number of ways to make sum at index i, i.e., minCoins(i, sum, coins), depends on the optimal solutions of the subproblems minCoins(i, sum-coins[i], coins) , and minCoins(i+1, sum, coins). By comparing these optimal substructures, we can efficiently calculate the minimum number of coins to make target sum at index i.
2. Overlapping Subproblems:
While applying a recursive approach in this problem, we notice that certain subproblems are computed multiple times.
- There are only are two parameters: i and sum that changes in the recursive solution. So we create a 2D matrix of size n*(sum+1) for memoization.
- We initialize this matrix as -1 to indicate nothing is computed initially.
- Now we modify our recursive solution to first check if the value is -1, then only make recursive calls. This way, we avoid re-computations of the same subproblems.
C++
// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;
int minCoinsRecur(int i, int sum, vector<int> &coins, vector<vector<int>> &memo) {
// base case
if (sum == 0) return 0;
if (sum <0 || i == coins.size()) return INT_MAX;
if (memo[i][sum]!=-1) return memo[i][sum];
int take = INT_MAX;
// take a coin only if its value
// is greater than 0.
if (coins[i]>0) {
take = minCoinsRecur(i, sum-coins[i], coins, memo);
if (take != INT_MAX) take++;
}
int noTake = minCoinsRecur(i+1, sum, coins, memo);
return memo[i][sum] = min(take, noTake);
}
int minCoins(vector<int> &coins, int sum) {
vector<vector<int>> memo(coins.size(), vector<int>(sum+1, -1));
int ans = minCoinsRecur(0, sum, coins, memo);
return ans!=INT_MAX?ans:-1;
}
int main() {
vector<int> coins = {9, 6, 5, 1};
int sum = 19;
cout << minCoins(coins, sum);
return 0;
}
// Java program to find minimum of coins
// to make a given change sum
import java.util.Arrays;
class GfG {
static int minCoinsRecur(int i, int sum, int[] coins, int[][] memo) {
// base case
if (sum == 0) return 0;
if (sum < 0 || i == coins.length) return Integer.MAX_VALUE;
if (memo[i][sum] != -1) return memo[i][sum];
int take = Integer.MAX_VALUE;
// take a coin only if its value
// is greater than 0.
if (coins[i] > 0) {
take = minCoinsRecur(i, sum - coins[i], coins, memo);
if (take != Integer.MAX_VALUE) take++;
}
int noTake = minCoinsRecur(i + 1, sum, coins, memo);
return memo[i][sum] = Math.min(take, noTake);
}
static int minCoins(int[] coins, int sum) {
int[][] memo = new int[coins.length][sum + 1];
for (int[] row : memo) Arrays.fill(row, -1);
int ans = minCoinsRecur(0, sum, coins, memo);
return ans != Integer.MAX_VALUE ? ans : -1;
}
public static void main(String[] args) {
int[] coins = {9, 6, 5, 1};
int sum = 19;
System.out.println(minCoins(coins, sum));
}
}
# Python program to find minimum of coins
# to make a given change sum
def minCoinsRecur(i, sum, coins, memo):
# base case
if sum == 0:
return 0
if sum < 0 or i == len(coins):
return float('inf')
if memo[i][sum] != -1:
return memo[i][sum]
take = float('inf')
# take a coin only if its value
# is greater than 0.
if coins[i] > 0:
take = minCoinsRecur(i, sum - coins[i], coins, memo)
if take != float('inf'):
take += 1
noTake = minCoinsRecur(i + 1, sum, coins, memo)
memo[i][sum] = min(take, noTake)
return memo[i][sum]
def minCoins(coins, sum):
memo = [[-1] * (sum + 1) for _ in range(len(coins))]
ans = minCoinsRecur(0, sum, coins, memo)
return ans if ans != float('inf') else -1
if __name__ == "__main__":
coins = [9, 6, 5, 1]
sum = 19
print(minCoins(coins, sum))
// C# program to find minimum of coins
// to make a given change sum
using System;
class GfG {
static int minCoinsRecur(int i, int sum, int[] coins, int[,] memo) {
// base case
if (sum == 0) return 0;
if (sum < 0 || i == coins.Length) return int.MaxValue;
if (memo[i, sum] != -1) return memo[i, sum];
int take = int.MaxValue;
// take a coin only if its value
// is greater than 0.
if (coins[i] > 0) {
take = minCoinsRecur(i, sum - coins[i], coins, memo);
if (take != int.MaxValue) take++;
}
int noTake = minCoinsRecur(i + 1, sum, coins, memo);
memo[i, sum] = Math.Min(take, noTake);
return memo[i, sum];
}
static int minCoins(int[] coins, int sum) {
int[,] memo = new int[coins.Length, sum + 1];
for (int i = 0; i < coins.Length; i++)
for (int j = 0; j <= sum; j++)
memo[i, j] = -1;
int ans = minCoinsRecur(0, sum, coins, memo);
return ans != int.MaxValue ? ans : -1;
}
static void Main(string[] args) {
int[] coins = { 9, 6, 5, 1 };
int sum = 19;
Console.WriteLine(minCoins(coins, sum));
}
}
// JavaScript program to find minimum of coins
// to make a given change sum
function minCoinsRecur(i, sum, coins, memo) {
// base case
if (sum === 0) return 0;
if (sum < 0 || i === coins.length) return Number.MAX_VALUE;
if (memo[i][sum] !== -1) return memo[i][sum];
let take = Number.MAX_VALUE;
// take a coin only if its value
// is greater than 0.
if (coins[i] > 0) {
take = minCoinsRecur(i, sum - coins[i], coins, memo);
if (take !== Number.MAX_VALUE) take++;
}
let noTake = minCoinsRecur(i + 1, sum, coins, memo);
memo[i][sum] = Math.min(take, noTake);
return memo[i][sum];
}
function minCoins(coins, sum) {
const memo = Array.from({ length: coins.length }, () => Array(sum + 1).fill(-1));
const ans = minCoinsRecur(0, sum, coins, memo);
return ans !== Number.MAX_VALUE ? ans : -1;
}
const coins = [9, 6, 5, 1];
const sum = 19;
console.log(minCoins(coins, sum));
Using Bottom-Up DP (Tabulation) – O(n*sum) Time and O(n*sum) Space
The idea is to fill the DP table based on previous values. For each coin, we either include it or exclude it to compute the minimum number of coins needed for each sum. The table is filled in an iterative manner from i = n-1 to i = 0 and for each sum from 1 to sum.
The dynamic programming relation is as follows:
- if (sum-coins[i]) is greater than 0, then dp[i][sum] = min(1+dp[i][sum-coins[i]], dp[i+1][sum])
- else dp[i][sum] = dp[i+1][sum].
C++
// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;
int minCoins(vector<int> &coins, int sum) {
vector<vector<int>> dp(coins.size(), vector<int>(sum+1, 0));
for (int i=coins.size()-1; i>=0; i--) {
for (int j=1; j<=sum; j++) {
dp[i][j] = INT_MAX;
int take = INT_MAX, noTake = INT_MAX;
// If we take coins[i] coin
if (j-coins[i]>=0) {
take = dp[i][j-coins[i]];
if (take != INT_MAX) take++;
}
if (i+1<coins.size())
noTake = dp[i+1][j];
dp[i][j] = min(take, noTake);
}
}
if (dp[0][sum]!=INT_MAX) return dp[0][sum];
return -1;
}
int main() {
vector<int> coins = {9, 6, 5, 1};
int sum = 19;
cout << minCoins(coins, sum);
return 0;
}
// Java program to find minimum of coins
// to make a given change sum
import java.util.Arrays;
class GfG {
static int minCoins(int[] coins, int sum) {
int[][] dp = new int[coins.length][sum + 1];
for (int i = coins.length - 1; i >= 0; i--) {
for (int j = 1; j <= sum; j++) {
dp[i][j] = Integer.MAX_VALUE;
int take = Integer.MAX_VALUE, noTake = Integer.MAX_VALUE;
// If we take coins[i] coin
if (j - coins[i] >= 0) {
take = dp[i][j - coins[i]];
if (take != Integer.MAX_VALUE) take++;
}
if (i + 1 < coins.length) noTake = dp[i + 1][j];
dp[i][j] = Math.min(take, noTake);
}
}
if (dp[0][sum] != Integer.MAX_VALUE) return dp[0][sum];
return -1;
}
public static void main(String[] args) {
int[] coins = {9, 6, 5, 1};
int sum = 19;
System.out.println(minCoins(coins, sum));
}
}
# Python program to find minimum of coins
# to make a given change sum
def minCoins(coins, sum):
dp = [[0] * (sum + 1) for _ in range(len(coins))]
for i in range(len(coins) - 1, -1, -1):
for j in range(1, sum + 1):
dp[i][j] = float('inf')
take = float('inf')
noTake = float('inf')
# If we take coins[i] coin
if j - coins[i] >= 0:
take = dp[i][j - coins[i]]
if take != float('inf'):
take += 1
if i + 1 < len(coins):
noTake = dp[i + 1][j]
dp[i][j] = min(take, noTake)
if dp[0][sum] != float('inf'):
return dp[0][sum]
return -1
if __name__ == "__main__":
coins = [9, 6, 5, 1]
sum = 19
print(minCoins(coins, sum))
// C# program to find minimum of coins
// to make a given change sum
using System;
class GfG {
static int minCoins(int[] coins, int sum) {
int[,] dp = new int[coins.Length, sum + 1];
for (int i = coins.Length - 1; i >= 0; i--) {
for (int j = 1; j <= sum; j++) {
dp[i, j] = int.MaxValue;
int take = int.MaxValue, noTake = int.MaxValue;
// If we take coins[i] coin
if (j - coins[i] >= 0) {
take = dp[i, j - coins[i]];
if (take != int.MaxValue) take++;
}
if (i + 1 < coins.Length) noTake = dp[i + 1, j];
dp[i, j] = Math.Min(take, noTake);
}
}
if (dp[0, sum] != int.MaxValue) return dp[0, sum];
return -1;
}
static void Main(string[] args) {
int[] coins = { 9, 6, 5, 1 };
int sum = 19;
Console.WriteLine(minCoins(coins, sum));
}
}
// JavaScript program to find minimum of coins
// to make a given change sum
function minCoins(coins, sum) {
let dp = Array.from({ length: coins.length }, () => Array(sum + 1).fill(0));
for (let i = coins.length - 1; i >= 0; i--) {
for (let j = 1; j <= sum; j++) {
dp[i][j] = Number.MAX_VALUE;
let take = Number.MAX_VALUE, noTake = Number.MAX_VALUE;
// If we take coins[i] coin
if (j - coins[i] >= 0) {
take = dp[i][j - coins[i]];
if (take !== Number.MAX_VALUE) take++;
}
if (i + 1 < coins.length) noTake = dp[i + 1][j];
dp[i][j] = Math.min(take, noTake);
}
}
if (dp[0][sum] !== Number.MAX_VALUE) return dp[0][sum];
return -1;
}
const coins = [9, 6, 5, 1];
const sum = 19;
console.log(minCoins(coins, sum));
Using Space Optimized DP – O(n*sum) Time and O(sum) Space
In previous approach of dynamic programming we have derive the relation between states as given below:
- if (sum-coins[i]) is greater than 0, then dp[i][sum] = min(1+dp[i][sum-coins[i]], dp[i+1][sum])
- else dp[i][sum] = dp[i+1][sum].
If we observe that for calculating current dp[i][sum] state we only need previous row dp[i-1][sum] or current row dp[i][sum-coins[i]]. There is no need to store all the previous states just one previous state is used to compute result.
C++
// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;
int minCoins(vector<int> &coins, int sum) {
vector<int> dp(sum+1, INT_MAX);
dp[0] = 0;
for (int i=coins.size()-1; i>=0; i--) {
for (int j=1; j<=sum; j++) {
int take = INT_MAX, noTake = INT_MAX;
// If we take coins[i] coin
if (j-coins[i]>=0 && coins[i]>0) {
take = dp[j-coins[i]];
if (take != INT_MAX) take++;
}
if (i+1<coins.size())
noTake = dp[j];
dp[j] = min(take, noTake);
}
}
if (dp[sum]!=INT_MAX) return dp[sum];
return -1;
}
int main() {
vector<int> coins = {9, 6, 5, 1};
int sum = 19;
cout << minCoins(coins, sum);
return 0;
}
// Java program to find minimum of coins
// to make a given change sum
import java.util.Arrays;
class GfG {
static int minCoins(int[] coins, int sum) {
int[] dp = new int[sum + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = coins.length - 1; i >= 0; i--) {
for (int j = 1; j <= sum; j++) {
int take = Integer.MAX_VALUE, noTake = Integer.MAX_VALUE;
// If we take coins[i] coin
if (j - coins[i] >= 0 && coins[i] > 0) {
take = dp[j - coins[i]];
if (take != Integer.MAX_VALUE) take++;
}
if (i + 1 < coins.length)
noTake = dp[j];
dp[j] = Math.min(take, noTake);
}
}
if (dp[sum] != Integer.MAX_VALUE) return dp[sum];
return -1;
}
public static void main(String[] args) {
int[] coins = {9, 6, 5, 1};
int sum = 19;
System.out.println(minCoins(coins, sum));
}
}
# Python program to find minimum of coins
# to make a given change sum
def minCoins(coins, sum):
dp = [float('inf')] * (sum + 1)
dp[0] = 0
for i in range(len(coins) - 1, -1, -1):
for j in range(1, sum + 1):
take = float('inf')
noTake = float('inf')
# If we take coins[i] coin
if j - coins[i] >= 0 and coins[i] > 0:
take = dp[j - coins[i]]
if take != float('inf'):
take += 1
if i + 1 < len(coins):
noTake = dp[j]
dp[j] = min(take, noTake)
return dp[sum] if dp[sum] != float('inf') else -1
if __name__ == "__main__":
coins = [9, 6, 5, 1]
sum = 19
print(minCoins(coins, sum))
// C# program to find minimum of coins
// to make a given change sum
using System;
class GfG {
static int minCoins(int[] coins, int sum) {
int[] dp = new int[sum + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
for (int i = coins.Length - 1; i >= 0; i--) {
for (int j = 1; j <= sum; j++) {
int take = int.MaxValue, noTake = int.MaxValue;
// If we take coins[i] coin
if (j - coins[i] >= 0 && coins[i] > 0) {
take = dp[j - coins[i]];
if (take != int.MaxValue) take++;
}
if (i + 1 < coins.Length)
noTake = dp[j];
dp[j] = Math.Min(take, noTake);
}
}
if (dp[sum] != int.MaxValue) return dp[sum];
return -1;
}
static void Main() {
int[] coins = { 9, 6, 5, 1 };
int sum = 19;
Console.WriteLine(minCoins(coins, sum));
}
}
// JavaScript program to find minimum of coins
// to make a given change sum
function minCoins(coins, sum) {
let dp = new Array(sum + 1).fill(Number.MAX_VALUE);
dp[0] = 0;
for (let i = coins.length - 1; i >= 0; i--) {
for (let j = 1; j <= sum; j++) {
let take = Number.MAX_VALUE, noTake = Number.MAX_VALUE;
// If we take coins[i] coin
if (j - coins[i] >= 0 && coins[i] > 0) {
take = dp[j - coins[i]];
if (take !== Number.MAX_VALUE) take++;
}
if (i + 1 < coins.length)
noTake = dp[j];
dp[j] = Math.min(take, noTake);
}
}
return dp[sum] !== Number.MAX_VALUE ? dp[sum] : -1;
}
let coins = [9, 6, 5, 1];
let sum = 19;
console.log(minCoins(coins, sum));
Similar Reads
Introduction to Knapsack Problem, its Types and How to solve them
The Knapsack problem is an example of the combinational optimization problem. This problem is also commonly known as the "Rucksack Problem". The name of the problem is defined from the maximization problem as mentioned below: Given a bag with maximum weight capacity of W and a set of items, each hav
6 min read
Fractional Knapsack
Fractional Knapsack Problem
Given the weights and profits of N items, in the form of {profit, weight} put these items in a knapsack of capacity W to get the maximum total profit in the knapsack. In Fractional Knapsack, we can break items for maximizing the total value of the knapsack. Input: arr[] = {{60, 10}, {100, 20}, {120,
8 min read
Fractional Knapsack Queries
Given an integer array, consisting of positive weights "W" and their values "V" respectively as a pair and some queries consisting of an integer 'C' specifying the capacity of the knapsack, find the maximum value of products that can be put in the knapsack if the breaking of items is allowed. Exampl
9 min read
Difference between 0/1 Knapsack problem and Fractional Knapsack problem
What is Knapsack Problem?Suppose you have been given a knapsack or bag with a limited weight capacity, and each item has some weight and value. The problem here is that "Which item is to be placed in the knapsack such that the weight limit does not exceed and the total value of the items is as large
13 min read
0/1 Knapsack
0/1 Knapsack Problem
Given N items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible. Note: The constraint
15+ min read
Printing Items in 0/1 Knapsack
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays, val[0..n-1] and wt[0..n-1] represent values and weights associated with n items respectively. Also given an integer W which repre
12 min read
0/1 Knapsack Problem to print all possible solutions
Given weights and profits of N items, put these items in a knapsack of capacity W. The task is to print all possible solutions to the problem in such a way that there are no remaining items left whose weight is less than the remaining capacity of the knapsack. Also, compute the maximum profit.Exampl
10 min read
0-1 knapsack queries
Given an integer array W[] consisting of weights of the items and some queries consisting of capacity C of knapsack, for each query find maximum weight we can put in the knapsack. Value of C doesn't exceed a certain integer C_MAX. Examples: Input: W[] = {3, 8, 9} q = {11, 10, 4} Output: 11 9 3 If C
12 min read
0/1 Knapsack using Branch and Bound
Given two arrays v[] and w[] that represent values and weights associated with n items respectively. Find out the maximum value subset(Maximum Profit) of v[] such that the sum of the weights of this subset is smaller than or equal to Knapsack capacity W. Note: The constraint here is we can either pu
15+ min read
0/1 Knapsack using Least Cost Branch and Bound
Given N items with weights W[0..n-1], values V[0..n-1] and a knapsack with capacity C, select the items such that: The sum of weights taken into the knapsack is less than or equal to C.The sum of values of the items in the knapsack is maximum among all the possible combinations.Examples: Input:
15+ min read
Unbounded Fractional Knapsack
Given the weights and values of n items, the task is to put these items in a knapsack of capacity W to get the maximum total value in the knapsack, we can repeatedly put the same item and we can also put a fraction of an item. Examples: Input: val[] = {14, 27, 44, 19}, wt[] = {6, 7, 9, 8}, W = 50 Ou
5 min read
Unbounded Knapsack (Repetition of items allowed)
Given a knapsack weight, say capacity and a set of n items with certain value vali and weight wti, The task is to fill the knapsack in such a way that we can get the maximum profit. This is different from the classical Knapsack problem, here we are allowed to use an unlimited number of instances of
15+ min read
Unbounded Knapsack (Repetition of items allowed) | Efficient Approach
Given an integer W, arrays val[] and wt[], where val[i] and wt[i] are the values and weights of the ith item, the task is to calculate the maximum value that can be obtained using weights not exceeding W. Note: Each weight can be included multiple times. Examples: Input: W = 4, val[] = {6, 18}, wt[]
8 min read
Double Knapsack | Dynamic Programming
Given an array arr[] containing the weight of 'n' distinct items, and two knapsacks that can withstand capactiy1 and capacity2 weights, the task is to find the sum of the largest subset of the array 'arr', that can be fit in the two knapsacks. It's not allowed to break any items in two, i.e. an item
15+ min read
Some Problems of Knapsack problem
Partition a Set into Two Subsets of Equal Sum
Given an array arr[], the task is to check if it can be partitioned into two parts such that the sum of elements in both parts is the same. Examples: Input: arr[] = [1, 5, 11, 5]Output: True Explanation: The array can be partitioned as [1, 5, 5] and [11] Input: arr[] = [1, 5, 3]Output: False Explana
15+ min read
Count of subsets with sum equal to target
Given an array arr[] of length n and an integer target, the task is to find the number of subsets with a sum equal to target. Examples: Input: arr[] = [1, 2, 3, 3], target = 6 Output: 3 Explanation: All the possible subsets are [1, 2, 3], [1, 2, 3] and [3, 3] Input: arr[] = [1, 1, 1, 1], target = 1
15+ min read
Length of longest subset consisting of A 0s and B 1s from an array of strings
Given an array arr[] consisting of binary strings, and two integers a and b, the task is to find the length of the longest subset consisting of at most a 0s and b 1s. Examples: Input: arr[] = ["1" ,"0" ,"0001" ,"10" ,"111001"], a = 5, b = 3Output: 4Explanation: One possible way is to select the subs
15+ min read
Breaking an Integer to get Maximum Product
Given a number n, the task is to break n in such a way that multiplication of its parts is maximized. Input : n = 10Output: 36Explanation: 10 = 4 + 3 + 3 and 4 * 3 * 3 = 36 is the maximum possible product. Input: n = 8Output: 18Explanation: 8 = 2 + 3 + 3 and 2 * 3 * 3 = 18 is the maximum possible pr
15+ min read
Coin Change - Minimum Coins to Make Sum
Given an array of coins[] of size n and a target value sum, where coins[i] represent the coins of different denominations. You have an infinite supply of each of the coins. The task is to find the minimum number of coins required to make the given value sum. If it's not possible to make a change, re
15+ min read
Coin Change - Count Ways to Make Sum
Given an integer array of coins[] of size n representing different types of denominations and an integer sum, the task is to count all combinations of coins to make a given value sum. Note: Assume that you have an infinite supply of each type of coin. Examples: Input: sum = 4, coins[] = [1, 2, 3]Out
15+ min read
Maximum sum of values of N items in 0-1 Knapsack by reducing weight of at most K items in half
Given weights and values of N items and the capacity W of the knapsack. Also given that the weight of at most K items can be changed to half of its original weight. The task is to find the maximum sum of values of N items that can be obtained such that the sum of weights of items in knapsack does no
15+ min read