Minimum cost of purchasing at least X chocolates

0 0 16 minutes read

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 chocolates
int 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 Code
int 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 approach
class GFG{
 
// Function to calculate minimum cost
// of buying least X chocolates
static 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 Code
public 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 chocolates
def 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 Code
if __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 approach
using 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

Time Complexity: O(2^N)
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 chocolates
int 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 chocolates
void 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 Code
int 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 approach
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 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 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] = 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 code
public 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 approach
import sys
 
# Recursive function to calculate minimum
# cost of buying at least X chocolates
def 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 chocolates
def 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 X
arr = [ [ 4, 3 ], [ 3, 2 ], [ 2, 4 ], [ 1, 3 ], [ 4, 2 ] ]
X = 7
 
# Store the size of the array
n = 5
 
findMinCost(arr, X, n)
 
# This code is contributed by decode2207.

C#

// C# program for the above approach
using 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

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 chocolates
void 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 Code
int 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 chocolates
def 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 Code
if __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 Code
const 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

Time Complexity: O(N*X)

Auxiliary Space: O(N*X)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!