Given array A[] and B[] of size N representing N type of operations. Given a number H, reduce this number to less than equal to 0 by performing the following operation at minimum cost. Choose ith operation and subtract A[i] from H and the cost incurred will be B[i]. Every operation can be performed any number of times.
Examples:
Input: A[] = {8, 4, 2}, B[] = {3, 2, 1}, H = 9
Output: 4
Explanation: The optimal way to solve this problem is to decrease the number H = 9 by the first operation reducing it by A[1] = 8 and the cost incurred is B[1] = 3. H is now 1. Use the third operation to reduce H = 1 by A[3] = 2 cost incurred will be B[3] = 1. Now H is -1 which is less than equal to 0 hence. in cost = 3 + 1 = 4 number H can be made less than equal to 0.Input: A[] = {1, 2, 3, 4, 5, 6}, B[] = {1, 3, 9, 27, 81, 243}, H = 100
Output: 100
Explanation: It is optimal to use the first operation 100 times to make H zero in minimum cost.
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(HN)
Auxiliary Space: O(1)
Another approach : Recursive + Memoization
In this approach we find our answer with the help of recursion but to avoid recomputing of same problem we use use a vector memo to store the computations of subproblems.
Implementation :
C++
#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost to make// number H less than or equal to zeroint findMinimumCost(int A[], int B[], int N, int H, vector<int>& memo){ // base case if (H <= 0) { return 0; } // check if the result is already computed if (memo[H] != -1) { return memo[H]; } int ans = INT_MAX; // recursive step for (int i = 0; i < N; i++) { ans = min(ans, findMinimumCost(A, B, N, H - A[i], memo) + B[i]); } // store the computed result in memo table memo[H] = ans; return ans;}// Driver Codeint main(){ // Test Case 1 int A[] = { 8, 4, 2 }, B[] = { 3, 2, 1 }, H = 9; int N = sizeof(A) / sizeof(A[0]); // Memo table to store the computed results vector<int> memo(H + 1, -1); // Function Call cout << findMinimumCost(A, B, N, H, memo) << endl; // Test Case 2 int A1[] = { 1, 2, 3, 4, 5, 6 }, B1[] = { 1, 3, 9, 27, 81, 243 }, H1 = 100; int N1 = sizeof(A1) / sizeof(A1[0]); // Memo table to store the computed results vector<int> memo1(H1 + 1, -1); // Function Call cout << findMinimumCost(A1, B1, N1, H1, memo1) << endl; return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to find the minimum cost to make // number H less than or equal to zero public static int findMinimumCost(int[] A, int[] B, int N, int H, int[] memo) { // base case if (H <= 0) { return 0; } // check if the result is already computed if (memo[H] != -1) { return memo[H]; } int ans = Integer.MAX_VALUE; // recursive step for (int i = 0; i < N; i++) { ans = Math.min(ans, findMinimumCost( A, B, N, H - A[i], memo) + B[i]); } // store the computed result in memo table memo[H] = ans; return ans; } // Driver Code public static void main(String[] args) { // Test Case 1 int[] A = { 8, 4, 2 }; int[] B = { 3, 2, 1 }; int H = 9; int N = A.length; // Memo table to store the computed results int[] memo = new int[H + 1]; Arrays.fill(memo, -1); // Function Call System.out.println( findMinimumCost(A, B, N, H, memo)); // Test Case 2 int[] A1 = { 1, 2, 3, 4, 5, 6 }; int[] B1 = { 1, 3, 9, 27, 81, 243 }; int H1 = 100; int N1 = A1.length; // Memo table to store the computed results int[] memo1 = new int[H1 + 1]; Arrays.fill(memo1, -1); // Function Call System.out.println( findMinimumCost(A1, B1, N1, H1, memo1)); }} |
Python
# Function to find the minimum cost to make# number H less than or equal to zerodef findMinimumCost(A, B, N, H, memo): # Base case if H <= 0: return 0 # Check if the result is already computed if memo[H] != -1: return memo[H] ans = float('inf') # Recursive step for i in range(N): ans = min(ans, findMinimumCost(A, B, N, H - A[i], memo) + B[i]) # Store the computed result in memo table memo[H] = ans return ans# Driver Codeif __name__ == "__main__": # Test Case 1 A = [8, 4, 2] B = [3, 2, 1] H = 9 N = len(A) # Memo table to store the computed results memo = [-1] * (H + 1) # Function Call print(findMinimumCost(A, B, N, H, memo)) # Test Case 2 A1 = [1, 2, 3, 4, 5, 6] B1 = [1, 3, 9, 27, 81, 243] H1 = 100 N1 = len(A1) # Memo table to store the computed results memo1 = [-1] * (H1 + 1) # Function Call print(findMinimumCost(A1, B1, N1, H1, memo1)) |
C#
using System;using System.Collections.Generic;class Gfg{ // Function to find the minimum cost to make // number H less than or equal to zero static int findMinimumCost(int[] A, int[] B, int N, int H, List<int> memo) { // Base case if (H <= 0) { return 0; } // Check if the result is already computed if (memo[H] != -1) { return memo[H]; } int ans = int.MaxValue; // Recursive step for (int i = 0; i < N; i++) { ans = Math.Min(ans, findMinimumCost(A, B, N, H - A[i], memo) + B[i]); } // Store the computed result in the memo table memo[H] = ans; return ans; } static void Main(string[] args) { // Test Case 1 int[] A = { 8, 4, 2 }; int[] B = { 3, 2, 1 }; int H = 9; int N = A.Length; // Memo table to store the computed results List<int> memo = new List<int>(new int[H + 1]); for (int i = 0; i <= H; i++) { memo[i] = -1; } // Function Call Console.WriteLine(findMinimumCost(A, B, N, H, memo)); // Test Case 2 int[] A1 = { 1, 2, 3, 4, 5, 6 }; int[] B1 = { 1, 3, 9, 27, 81, 243 }; int H1 = 100; int N1 = A1.Length; // Memo table to store the computed results List<int> memo1 = new List<int>(new int[H1 + 1]); for (int i = 0; i <= H1; i++) { memo1[i] = -1; } // Function Call Console.WriteLine(findMinimumCost(A1, B1, N1, H1, memo1)); }} |
Javascript
// Function to find the minimum cost to make// number H less than or equal to zerofunction findMinimumCost(A, B, N, H, memo){ // base case if (H <= 0) { return 0; } // check if the result is already computed if (memo[H] != -1) { return memo[H]; } let ans = Number.MAX_VALUE; // recursive step for (let i = 0; i < N; i++) { ans = Math.min(ans, findMinimumCost(A, B, N, H - A[i], memo) + B[i]); } // store the computed result in memo table memo[H] = ans; return ans;}// Test Case 1let A = [ 8, 4, 2 ], B = [ 3, 2, 1 ], H = 9;let N = A.length;// Memo table to store the computed resultslet memo=new Array(H + 1).fill(-1);// Function Callconsole.log(findMinimumCost(A, B, N, H, memo));// Test Case 2let A1 = [ 1, 2, 3, 4, 5, 6 ], B1 = [ 1, 3, 9, 27, 81, 243 ], H1 = 100;let N1 = A1.length;// Memo table to store the computed resultslet memo1=new Array(H1 + 1).fill(-1);// Function Callconsole.log(findMinimumCost(A1, B1, N1, H1, memo1)); |
Output
4 100
Time Complexity: O(N * H)
Auxiliary Space: O(H)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
- dp[i] represents a minimum cost to make I zero from given operations
- recurrence relation: dp[i] = min(dp[i], dp[max(0, i – A[i])] + B[i])
Follow the steps below to solve the problem:
- Declare a dp table of size H + 1 with all values initialized to infinity
- Base case dp[0] = 0
- Iterate from 1 to H to calculate a value for each of them and to do that use all operations from 0 to j and try to make i zero by the minimum cost of these operations.
- Finally, return minimum cost dp[H]
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Minimum cost to make number H// less than equal to zeroint findMinimumCost(int A[], int B[], int N, int H){ // Declaring dp array initially all values // infinity vector<int> dp(H + 1, INT_MAX); // base case dp[0] = 0; // Calculating minimum cost for each i // from 1 to H for (int i = 1; i <= H; i++) { for (int j = 0; j < N; j++) { dp[i] = min(dp[i], dp[max(0, i - A[j])] + B[j]); } } // Returning the answer return dp[H];}// Driver Codeint main(){ // Test Case 1 int A[] = { 8, 4, 2 }, B[] = { 3, 2, 1 }, H = 9; int N = sizeof(A) / sizeof(A[0]); // Function Call cout << findMinimumCost(A, B, N, H) << endl; // Test Case 2 int A1[] = { 1, 2, 3, 4, 5, 6 }, B1[] = { 1, 3, 9, 27, 81, 243 }, H1 = 100; int N1 = sizeof(A1) / sizeof(A1[0]); // Function Call cout << findMinimumCost(A1, B1, N1, H1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Minimum cost to make number H // less than equal to zero public static int findMinimumCost(int A[], int B[], int N, int H) { // Declaring dp array initially all values // infinity int dp[] = new int[H + 1]; for (int i = 0; i < H + 1; i++) dp[i] = Integer.MAX_VALUE; // base case dp[0] = 0; // Calculating minimum cost for each i // from 1 to H for (int i = 1; i <= H; i++) { for (int j = 0; j < N; j++) { int x = Math.max(0, i - A[j]); dp[i] = Math.min(dp[i], dp[x] + B[j]); } } // Returning the answer return dp[H]; } // Driver Code public static void main(String[] args) { // Test Case 1 int A[] = { 8, 4, 2 }, B[] = { 3, 2, 1 }, H = 9; int N = A.length; // Function Call System.out.println(findMinimumCost(A, B, N, H)); // Test Case 2 int A1[] = { 1, 2, 3, 4, 5, 6 }, B1[] = { 1, 3, 9, 27, 81, 243 }, H1 = 100; int N1 = A1.length; // Function Call System.out.println(findMinimumCost(A1, B1, N1, H1)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approachimport sys# Minimum cost to make number H# less than equal to zerodef findMinimumCost(A, B, N, H): # Declaring dp array initially all values # infinity dp =[sys.maxsize]*(H + 1) # base case dp[0]= 0 # Calculating minimum cost for each i # from 1 to H for i in range(1, H + 1): for j in range(N): dp[i] = min(dp[i], dp[max(0, i - A[j])] + B[j]) # Returning the answer return dp[H] # Driver Code# Test Case 1A =[8, 4, 2]B =[3, 2, 1]H = 9N = len(A)# Function Callprint(findMinimumCost(A, B, N, H))# Test Case 2A1 =[1, 2, 3, 4, 5, 6]B1 =[1, 3, 9, 27, 81, 243]H1 = 100N1 = len(A)# Function Callprint(findMinimumCost(A1, B1, N1, H1))# This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class Gfg { // Minimum cost to make number H // less than equal to zero static int findMinimumCost(int[] A, int[] B, int N, int H) { // Declaring dp array initially all values // infinity // vector<int> dp(H + 1, INT_MAX); int[] dp = new int[H + 1]; for (int i = 0; i < H + 1; i++) dp[i] = 2147483647; // base case dp[0] = 0; // Calculating minimum cost for each i // from 1 to H for (int i = 1; i <= H; i++) { for (int j = 0; j < N; j++) { int x = Math.Max(0, i - A[j]); dp[i] = Math.Min(dp[i], dp[x] + B[j]); } } // Returning the answer return dp[H]; } // Driver Code public static void Main(string[] args) { // Test Case 1 int[] A = { 8, 4, 2 }; int[] B = { 3, 2, 1 }; int H = 9; int N = A.Length; // Function Call Console.WriteLine(findMinimumCost(A, B, N, H)); // Test Case 2 int[] A1 = { 1, 2, 3, 4, 5, 6 }; int[] B1 = { 1, 3, 9, 27, 81, 243 }; int H1 = 100; int N1 = A1.Length; // Function Call Console.WriteLine(findMinimumCost(A1, B1, N1, H1)); }}// This code is contributed by poojaagarwal2. |
Javascript
// JS code to implement the approach // Minimum cost to make number H // less than equal to zero function findMinimumCost(A, B, N, H) { // Declaring dp array initially all values // infinity let dp = new Array(H + 1).fill(Number.MAX_VALUE); // base case dp[0] = 0; // Calculating minimum cost for each i // from 1 to H for (let i = 1; i <= H; i++) { for (let j = 0; j < N; j++) { let x = Math.max(0, i - A[j]); dp[i] = Math.min(dp[i], dp[x] + B[j]); } } // Returning the answer return dp[H]; } // Driver Code // Test Case 1 let A = [8, 4, 2], B = [3, 2, 1], H = 9; let N = A.length; // Function Call console.log(findMinimumCost(A, B, N, H) + "<br>"); // Test Case 2 let A1 = [1, 2, 3, 4, 5, 6], B1 = [1, 3, 9, 27, 81, 243], H1 = 100; let N1 = A1.length; // Function Call console.log(findMinimumCost(A1, B1, N1, H1) + "<br>");// This code is contributed by Potta Lokesh |
Output
4 100
Time Complexity: O(N * H)
Auxiliary Space: O(N * H)
Related Articles:
- Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials
- Introduction to Arrays – Data Structures and Algorithms
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!
