Given a positive integer X and an array arr[] consisting of N pairs, where each pair (A, B) represents a box, where A represents the number of chocolates and B represents the cost of the current box. The task is to find the minimum cost to buy at least X number of chocolates.
Examples:
Input: arr[] = {{4, 3}, {3, 2}, {2, 4}, {1, 3}, {4, 2}}, X = 7
Output: 4
Examples: Select the 2nd and the 5th box. Number of chocolates = 3 + 4 = 7.
Total cost = 2 + 2 = 4, which is the minimum cost to buy at least 7 chocolates.Input: arr[] = {{10, 2}, {5, 3}}, X = 20
Output: -1
Examples: There exists no set of boxes which satisfies the given condition.
Naive Approach: The simplest approach is to use recursion, to consider all subsets of boxes and calculate the cost and number of chocolates of all subsets. From all such subsets, pick the subset having the minimum cost and at least X chocolates.
Optimal Sub-structure: To consider all subsets of items, there can be two cases for every box.
- Case 1: The item is included in the optimal subset. If the current box is included, then add the cost of this box and decrement X by the number of chocolates in the current box. And recur for the remaining X chocolates moving to the next index.
- Case 2: The item is not included in the optimal set. If the current box is not included, then just recur for the remaining X chocolates moving to the next index.
Therefore, the minimum cost that can be obtained is the minimum of the above two cases. Handle the base case if X ≤ 0, return 0.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate minimum cost// of buying least X chocolatesint findMinCost(pair<int, int> arr[], int X, int n, int i = 0){ // Base Case if (X <= 0) return 0; if (i >= n) return INT_MAX; // Include the i-th box int inc = findMinCost(arr, X - arr[i].first, n, i + 1); if (inc != INT_MAX) inc += arr[i].second; // Exclude the i-th box int exc = findMinCost(arr, X, n, i + 1); // Return the minimum of // the above two cases return min(inc, exc);}// Driver Codeint main(){ // Given array and value of X pair<int, int> arr[] = { { 4, 3 }, { 3, 2 }, { 2, 4 }, { 1, 3 }, { 4, 2 } }; int X = 7; // Store the size of the array int n = sizeof(arr) / sizeof(arr[0]); int ans = findMinCost(arr, X, n); // Print the answer if (ans != INT_MAX) cout << ans; else cout << -1; return 0;} |
Java
// Java program for above approachclass GFG{// Function to calculate minimum cost// of buying least X chocolatesstatic int findMinCost(int[][] arr, int X, int n, int i){ // Base Case if (X <= 0) return 0; if (i >= n) return Integer.MAX_VALUE; // Include the i-th box int inc = findMinCost(arr, X - arr[i][0], n, i + 1); if (inc != Integer.MAX_VALUE) inc += arr[i][1]; // Exclude the i-th box int exc = findMinCost(arr, X, n, i + 1); // Return the minimum of // the above two cases return Math.min(inc, exc);}// Driver Codepublic static void main(String[] args){ // Given array and value of X int[][] arr = { { 4, 3 }, { 3, 2 }, { 2, 4 }, { 1, 3 }, { 4, 2 } }; int X = 7; // Store the size of the array int n = arr.length; int ans = findMinCost(arr, X, n, 0); // Print the answer if (ans != Integer.MAX_VALUE) System.out.println(ans); else System.out.println(-1);}}// This code is contributed by Hritik |
Python3
# Python3 program for the above approach# Function to calculate minimum cost# of buying least X chocolatesdef findMinCost(arr,X, n, i = 0): # Base Case if (X <= 0): return 0 if (i >= n): return 10**8 # Include the i-th box inc = findMinCost(arr,X - arr[i][0], n, i + 1) if (inc != 10**8): inc += arr[i][1] # Exclude the i-th box exc = findMinCost(arr, X, n, i + 1) # Return the minimum of # the above two cases return min(inc, exc)# Driver Codeif __name__ == '__main__': # Given array and value of X arr = [[ 4, 3 ], [ 3, 2 ],[ 2, 4 ], [ 1, 3 ], [ 4, 2 ]] X = 7 # Store the size of the array n = len(arr) ans = findMinCost(arr, X, n) # Print answer if (ans != 10**8): print(ans) else: print(-1) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate minimum cost // of buying least X chocolates static int findMinCost(int[, ] arr, int X, int n, int i = 0) { // Base Case if (X <= 0) return 0; if (i >= n) return Int32.MaxValue; // Include the i-th box int inc = findMinCost(arr, X - arr[i, 0], n, i + 1); if (inc != Int32.MaxValue) inc += arr[i, 1]; // Exclude the i-th box int exc = findMinCost(arr, X, n, i + 1); // Return the minimum of // the above two cases return Math.Min(inc, exc); } // Driver Code public static void Main() { // Given array and value of X int[, ] arr = { { 4, 3 }, { 3, 2 }, { 2, 4 }, { 1, 3 }, { 4, 2 } }; int X = 7; // Store the size of the array int n = arr.GetLength(0); int ans = findMinCost(arr, X, n); // Print the answer if (ans != Int32.MaxValue) Console.Write(ans); else Console.Write(-1); }}// This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach // Function to calculate minimum cost // of buying least X chocolates function findMinCost( arr, X, n, i = 0) { // Base Case if (X <= 0) return 0; if (i >= n) return Number.MAX_SAFE_INTEGER; // Include the i-th box let inc = findMinCost(arr, X - arr[i][0], n, i + 1); if (inc != Number.MAX_SAFE_INTEGER) inc += arr[i][1]; // Exclude the i-th box let exc = findMinCost(arr, X, n, i + 1); // Return the minimum of // the above two cases return Math.min(inc, exc); } // Driver Code // Given array and value of X let arr = [ [ 4, 3 ], [ 3, 2 ], [ 2, 4 ], [ 1, 3 ], [ 4, 2 ] ]; let X = 7; // Store the size of the array let n = arr.length; let ans = findMinCost(arr, X, n); // Print the answer if (ans != Number.MAX_SAFE_INTEGER) document.write(ans) else document.write(-1) // This code is contributed by Hritik </script> |
Output
4
Time Complexity: O(2N)
Auxiliary Space: O(1)
Another Approach: To optimize the above approach, the idea is to use dynamic programming since the problem contains overlapping subproblems and optimal substructure property. The idea is to use memoization to solve the problem. Create a 2D array, dp[N][X] to store the results in the recursive calls. If a particular state is already computed, then return its result stored in the table in constant time.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to calculate minimum// cost of buying at least X chocolatesint findMinCostUtil(pair<int, int> arr[], int X, int n, int** dp, int i = 0){ // Base cases if (X <= 0) return 0; if (i >= n) return INT_MAX; // If the state is already computed, // return its result from the 2D array if (dp[i][X] != INT_MAX) return dp[i][X]; // Include the i-th box int inc = findMinCostUtil(arr, X - arr[i].first, n, dp, i + 1); if (inc != INT_MAX) inc += arr[i].second; // Exclude the i-th box int exc = findMinCostUtil(arr, X, n, dp, i + 1); // Update the result of // the state in 2D array dp[i][X] = min(inc, exc); // Return the result return dp[i][X];}// Function to find the minimum// cost to buy at least X chocolatesvoid findMinCost(pair<int, int> arr[], int X, int n){ // Create a 2D array, dp[][] int** dp = new int*[n + 1]; // Initialize entries with INT_MAX for (int i = 0; i <= n; i++) { dp[i] = new int[X + 1]; for (int j = 0; j <= X; j++) // Update dp[i][j] dp[i][j] = INT_MAX; } // Stores the minimum cost required int ans = findMinCostUtil(arr, X, n, dp); // Print the answer if (ans != INT_MAX) cout << ans; else cout << -1;}// Driver Codeint main(){ // Given array and value of X pair<int, int> arr[] = { { 4, 3 }, { 3, 2 }, { 2, 4 }, { 1, 3 }, { 4, 2 } }; int X = 7; // Store the size of the array int n = sizeof(arr) / sizeof(arr[0]); findMinCost(arr, X, n); return 0;} |
Java
// Java program for the above approachclass GFG{ // Recursive function to calculate minimum// cost of buying at least X chocolatesstatic int findMinCostUtil(int[][] arr, int X, int n, int[][] dp, int i){ // Base cases if (X <= 0) return 0; if (i >= n) return Integer.MAX_VALUE; // If the state is already computed, // return its result from the 2D array if (dp[i][X] != Integer.MAX_VALUE) return dp[i][X]; // Include the i-th box int inc = findMinCostUtil(arr, X - arr[i][0], n, dp, i + 1); if (inc != Integer.MAX_VALUE) inc += arr[i][1]; // Exclude the i-th box int exc = findMinCostUtil(arr, X, n, dp, i + 1); // Update the result of // the state in 2D array dp[i][X] = Math.min(inc, exc); // Return the result return dp[i][X];} // Function to find the minimum// cost to buy at least X chocolatesstatic void findMinCost(int[][] arr, int X, int n){ // Create a 2D array, dp[][] int[][] dp = new int[n + 1][X + 1]; // Initialize entries with INT_MAX for(int i = 0; i <= n; i++) { for(int j = 0; j <= X; j++) // Update dp[i][j] dp[i][j] = Integer.MAX_VALUE; } // Stores the minimum cost required int ans = findMinCostUtil(arr, X, n, dp, 0); // Print the answer if (ans != Integer.MAX_VALUE) System.out.println(ans); else System.out.println(-1);}// Driver codepublic static void main(String[] args) { // Given array and value of X int[][] arr = { { 4, 3 }, { 3, 2 }, { 2, 4 }, { 1, 3 }, { 4, 2 } }; int X = 7; // Store the size of the array int n = 5; findMinCost(arr, X, n);}}// This code is contributed by rameshtravel07 |
Python3
# Python3 program for the above approachimport sys# Recursive function to calculate minimum# cost of buying at least X chocolatesdef findMinCostUtil(arr, X, n, dp, i): # Base cases if (X <= 0): return 0 if (i >= n): return sys.maxsize # If the state is already computed, # return its result from the 2D array if (dp[i][X] != sys.maxsize): return dp[i][X] # Include the i-th box inc = findMinCostUtil(arr, X - arr[i][0], n, dp, i + 1) if (inc != sys.maxsize): inc += arr[i][1] # Exclude the i-th box exc = findMinCostUtil(arr, X, n, dp, i + 1) # Update the result of # the state in 2D array dp[i][X] = min(inc, exc) # Return the result return dp[i][X]# Function to find the minimum# cost to buy at least X chocolatesdef findMinCost(arr, X, n): # Create a 2D array, dp[][] dp = [[sys.maxsize for i in range(X+1)] for j in range(n+1)] # Stores the minimum cost required ans = findMinCostUtil(arr, X, n, dp, 0) # Print the answer if (ans != sys.maxsize): print(ans) else: print(-1) # Given array and value of Xarr = [ [ 4, 3 ], [ 3, 2 ], [ 2, 4 ], [ 1, 3 ], [ 4, 2 ] ]X = 7# Store the size of the arrayn = 5findMinCost(arr, X, n)# This code is contributed by decode2207. |
C#
// C# program for the above approachusing System;class GFG{ // Recursive function to calculate minimum // cost of buying at least X chocolates static int findMinCostUtil(int[,] arr, int X, int n, int[,] dp, int i) { // Base cases if (X <= 0) return 0; if (i >= n) return Int32.MaxValue; // If the state is already computed, // return its result from the 2D array if (dp[i,X] != Int32.MaxValue) return dp[i,X]; // Include the i-th box int inc = findMinCostUtil(arr, X - arr[i,0], n, dp, i + 1); if (inc != Int32.MaxValue) inc += arr[i,1]; // Exclude the i-th box int exc = findMinCostUtil(arr, X, n, dp, i + 1); // Update the result of // the state in 2D array dp[i,X] = Math.Min(inc, exc); // Return the result return dp[i,X]; } // Function to find the minimum // cost to buy at least X chocolates static void findMinCost(int[,] arr, int X, int n) { // Create a 2D array, dp[][] int[,] dp = new int[n + 1, X + 1]; // Initialize entries with INT_MAX for (int i = 0; i <= n; i++) { for (int j = 0; j <= X; j++) // Update dp[i][j] dp[i,j] = Int32.MaxValue; } // Stores the minimum cost required int ans = findMinCostUtil(arr, X, n, dp, 0); // Print the answer if (ans != Int32.MaxValue) Console.WriteLine(ans); else Console.WriteLine(-1); } static void Main () { // Given array and value of X int[,] arr = { { 4, 3 }, { 3, 2 }, { 2, 4 }, { 1, 3 }, { 4, 2 } }; int X = 7; // Store the size of the array int n = 5; findMinCost(arr, X, n); }}// This code is contributed by suresh07. |
Javascript
<script> // Javascript program for the above approach // Recursive function to calculate minimum // cost of buying at least X chocolates function findMinCostUtil(arr, X, n, dp, i) { // Base cases if (X <= 0) return 0; if (i >= n) return Number.MAX_VALUE; // If the state is already computed, // return its result from the 2D array if (dp[i][X] != Number.MAX_VALUE) return dp[i][X]; // Include the i-th box let inc = findMinCostUtil(arr, X - arr[i][0], n, dp, i + 1); if (inc != Number.MAX_VALUE) inc += arr[i][1]; // Exclude the i-th box let exc = findMinCostUtil(arr, X, n, dp, i + 1); // Update the result of // the state in 2D array dp[i][X] = Math.min(inc, exc); // Return the result return dp[i][X]; } // Function to find the minimum // cost to buy at least X chocolates function findMinCost(arr, X, n) { // Create a 2D array, dp[][] let dp = new Array(n + 1); // Initialize entries with INT_MAX for(let i = 0; i <= n; i++) { dp[i] = new Array(X + 1); for(let j = 0; j <= X; j++) // Update dp[i][j] dp[i][j] = Number.MAX_VALUE; } // Stores the minimum cost required let ans = findMinCostUtil(arr, X, n, dp, 0); // Print the answer if (ans != Number.MAX_VALUE) document.write(ans); else document.write(-1); } // Given array and value of X let arr = [ [ 4, 3 ], [ 3, 2 ], [ 2, 4 ], [ 1, 3 ], [ 4, 2 ] ]; let X = 7; // Store the size of the array let n = 5; findMinCost(arr, X, n);</script> |
Output
4
Time Complexity: O(N * X)
Auxiliary Space: O(N * X)
Efficient approach: Using the DP Tabulation method ( Iterative approach )
The approach to solving this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because the memorization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a 2D array dp[][] of size (n+1) x (X+1), where n is the size of the given array arr[] and X is the minimum number of chocolates to be bought.
- Initialize all the entries of the array with INT_MAX to mark them as unreachable.
- Set the base case of dp[0][0] as 0, as the minimum cost to buy 0 chocolates is 0.
- Iterate through the array arr[] and through the range of X.
- Update dp[i][j] as the minimum of dp[i-1][j] and dp[i-1][j-arr[i-1].first] + arr[i-1].second if j >= arr[i-1].first, where arr[i-1].first is the cost of the ith chocolate and arr[i-1].second is the sweetness level of the ith chocolate.
- Print the minimum cost as dp[n][X] if it is not equal to INT_MAX, else print -1.
Implementation :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// cost to buy at least X chocolatesvoid findMinCost(pair<int, int> arr[], int X, int n){ // Create a 2D array, dp[][] int dp[n + 1][X + 1]; // Initialize entries with INT_MAX for (int i = 0; i <= n; i++) { for (int j = 0; j <= X; j++) { dp[i][j] = INT_MAX; } } // Base cases dp[0][0] = 0; // Fill the table using bottom-up approach for (int i = 1; i <= n; i++) { for (int j = 0; j <= X; j++) { dp[i][j] = dp[i - 1][j]; if (j >= arr[i - 1].first) { int inc = dp[i - 1][j - arr[i - 1].first]; if (inc != INT_MAX) { dp[i][j] = min(dp[i][j], inc + arr[i - 1].second); } } } } // Print the answer if (dp[n][X] != INT_MAX) { cout << dp[n][X]; } else { cout << -1; }}// Driver Codeint main(){ // Given array and value of X pair<int, int> arr[] = { { 4, 3 }, { 3, 2 }, { 2, 4 }, { 1, 3 }, { 4, 2 } }; int X = 7; // Store the size of the array int n = sizeof(arr) / sizeof(arr[0]); findMinCost(arr, X, n); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function to find the minimum cost to buy at least X chocolates static void findMinCost(Pair[] arr, int X, int n) { // Create a 2D array, dp[][] int[][] dp = new int[n + 1][X + 1]; // Initialize entries with Integer.MAX_VALUE for (int i = 0; i <= n; i++) { for (int j = 0; j <= X; j++) { dp[i][j] = Integer.MAX_VALUE; } } // Base cases dp[0][0] = 0; // Fill the table using bottom-up approach for (int i = 1; i <= n; i++) { for (int j = 0; j <= X; j++) { dp[i][j] = dp[i - 1][j]; if (j >= arr[i - 1].first) { int inc = dp[i - 1][j - arr[i - 1].first]; if (inc != Integer.MAX_VALUE) { dp[i][j] = Math.min(dp[i][j], inc + arr[i - 1].second); } } } } // Print the answer if (dp[n][X] != Integer.MAX_VALUE) { System.out.println(dp[n][X]); } else { System.out.println(-1); } } // Driver code public static void main(String[] args) { // Given array and value of X Pair[] arr = { new Pair(4, 3), new Pair(3, 2), new Pair(2, 4), new Pair(1, 3), new Pair(4, 2) }; int X = 7; // Store the size of the array int n = arr.length; findMinCost(arr, X, n); } // Class to represent pair of integers static class Pair { int first, second; Pair(int a, int b) { first = a; second = b; } }} |
Python3
# Function to find the minimum# cost to buy at least X chocolatesdef findMinCost(arr, X, n): # Create a 2D array, dp[][] dp = [[float('inf') for j in range(X+1)] for i in range(n+1)] # Base cases dp[0][0] = 0 # Fill the table using bottom-up approach for i in range(1, n+1): for j in range(X+1): dp[i][j] = dp[i-1][j] if j >= arr[i-1][0]: inc = dp[i-1][j-arr[i-1][0]] if inc != float('inf'): dp[i][j] = min(dp[i][j], inc + arr[i-1][1]) # Print the answer if dp[n][X] != float('inf'): print(dp[n][X]) else: print(-1)# Driver Codeif __name__ == '__main__': # Given array and value of X arr = [(4, 3), (3, 2), (2, 4), (1, 3), (4, 2)] X = 7 # Store the size of the array n = len(arr) findMinCost(arr, X, n) |
C#
using System;public class Program{ // Function to find the minimum cost to buy at least X chocolates public static void FindMinCost(Tuple<int, int>[] arr, int X, int n) { // Create a 2D array, dp[][] int[,] dp = new int[n + 1, X + 1]; // Initialize entries with int.MaxValue for (int i = 0; i <= n; i++) { for (int j = 0; j <= X; j++) { dp[i, j] = int.MaxValue; } } // Base cases dp[0, 0] = 0; // Fill the table using bottom-up approach for (int i = 1; i <= n; i++) { for (int j = 0; j <= X; j++) { dp[i, j] = dp[i - 1, j]; if (j >= arr[i - 1].Item1) { int inc = dp[i - 1, j - arr[i - 1].Item1]; if (inc != int.MaxValue) { dp[i, j] = Math.Min(dp[i, j], inc + arr[i - 1].Item2); } } } } // Print the answer if (dp[n, X] != int.MaxValue) { Console.WriteLine(dp[n, X]); } else { Console.WriteLine(-1); } } // Driver Code public static void Main() { // Given array and value of X Tuple<int, int>[] arr = { Tuple.Create(4, 3), Tuple.Create(3, 2), Tuple.Create(2, 4), Tuple.Create(1, 3), Tuple.Create(4, 2) }; int X = 7; // Store the size of the array int n = arr.Length; FindMinCost(arr, X, n); }} |
Javascript
function findMinCost(arr, X, n) { // Create a 2D array, dp[][] const dp = new Array(n + 1).fill().map(() => new Array(X + 1).fill(Infinity)); // Base cases dp[0][0] = 0; // Fill the table using bottom-up approach for (let i = 1; i <= n; i++) { for (let j = 0; j <= X; j++) { dp[i][j] = dp[i - 1][j]; if (j >= arr[i - 1][0]) { const inc = dp[i - 1][j - arr[i - 1][0]]; if (inc !== Infinity) { dp[i][j] = Math.min(dp[i][j], inc + arr[i - 1][1]); } } } } // Print the answer if (dp[n][X] !== Infinity) { console.log(dp[n][X]); } else { console.log(-1); }}// Driver Codeconst arr = [ [4, 3], [3, 2], [2, 4], [1, 3], [4, 2],];const X = 7;const n = arr.length;findMinCost(arr, X, n);// This code is contributed by sarojmcy2e |
Output
4
Time Complexity: O(N*X)
Auxiliary Space: O(N*X)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
