Given 2 arrays num[] and cost[] containing the number of elements and the cost to buy that many elements respectively. {i.e. cost[i] is the cost to buy num[i] elements}. The task is to minimize the cost to buy exactly N elements.
Examples:
Input: num[] = [1, 2, 10, 50], cost[] = [400, 750, 3250, 15000], N = 7
Output: 2650
Explanation: The minimum amount needed to buy 7 pizzas is 2650.
You can order 3 units of 2 pizzas and 1 unit of 1 pizza.Input: num[] = [1, 2, 10, 50], cost[] = [400, 750, 3250, 15000], N = 15
Output: 5150
Explanation: The minimum amount needed to buy 15 pizzas is 5150.
You can order 1 unit of 10 pizzas, 2 units of 2 pizzas and 1 unit of 1 pizza.
Approach: The problem can be solved using recursion based on the following idea:
For each element of the num, we are having two choices whether to include that particular combo or not.
- Case 1: When the elements present at num[i] gets include in final result, the cost to these will get add up in our total cost and the total elements will get reduced by the number of pizzas brought.
- Case 2: When the element in num present at num[i] does not get included in final result, no cost will get add up in our total cost.
You can include elements if and only if the elements at num[i] is less than or equal to the total available.
Follow the steps mentioned below to implement the idea:
- Create a recursive function.
- For each call, there are two choices for the element as mentioned above.
- Calculate the value of all possible cases as mentioned above.
- The minimum among them is the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function for finding out the minimum costint min_cost(int i, int num[], int cost[], int n){ // Base case if (n == 0) return cost[i]; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return 1e9; } // Case where we are not including the elements // present at num[i] int not_take = min_cost(i - 1, num, cost, n); // Case where we are including the elements // present at num[i]. int take = INT_MAX; if (num[i] <= n) { // Calling recursion again for index i because of // the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i]); } // Returning the minimum of both i.e. // take and not take case return min(take, not_take);}// Driver codeint main(){ int N = 7; int num[4] = { 1, 2, 10, 50 }; int cost[4] = { 400, 750, 3250, 15000 }; // Function call cout << min_cost(3, num, cost, N); return 0;} |
Java
// java code to implement the approachimport java.io.*;import java.util.Scanner;class GFG { static int min_cost(int i, int []num, int []cost, int n) { // Base case if (n == 0) return cost[i]; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return (int)1e9; } // Case where we are not including the elements // present at num[i] int not_take = min_cost(i - 1, num, cost, n); // Case where we are including the elements // present at num[i]. int take = Integer.MAX_VALUE; if (num[i] <= n) { // Calling recursion again for index i because of // the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i]); } // Returning the minimum of both i.e. // take and not take case return Math.min(take, not_take); } public static void main(String[] args) { int N = 7; int[] num = new int[]{ 1, 2, 10, 50 }; int[] cost = new int[]{ 400, 750, 3250, 15000 }; // Function call System.out.println(min_cost(3, num, cost, N)); }}// this code is contributed by ksam2400 |
Python3
# Python code to implement the approachdef min_cost(i, num, cost, n): # Base case if n is 0: return cost[i] if i is 0: if num[0] <= n: return cost[0] * n else: return int(1e9) # Case where we are not including the elements present at num[i] not_take = min_cost(i-1, num, cost, n) # Case where we are including the elements present at num[i] take = float("inf") if num[i] <= n: # Calling recursion again for index i because of the infinite supply available. take = cost[i] + min_cost(i, num, cost, n-num[i]) # Returning the minimum of both i.e. take and not take case return min(take, not_take)N = 7num = [1, 2, 10, 50]cost = [400, 750, 3250, 15000]# Function callprint(min_cost(3, num, cost, N))# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;public class GFG { static int min_cost(int i, int[] num, int[] cost, int n) { // Base case if (n == 0) return cost[i]; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return (int)1e9; } // Case where we are not including the elements // present at num[i] int not_take = min_cost(i - 1, num, cost, n); // Case where we are including the elements // present at num[i]. int take = Int32.MaxValue; if (num[i] <= n) { // Calling recursion again for index i because // of the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i]); } // Returning the minimum of both i.e. // take and not take case return Math.Min(take, not_take); } // Driver Code static public void Main() { int N = 7; int[] num = { 1, 2, 10, 50 }; int[] cost = { 400, 750, 3250, 15000 }; // Function call Console.WriteLine(min_cost(3, num, cost, N)); }}// This code is contributed by Rohit Pradhan |
Javascript
<script> // JavaScript code for the above approach // Function for finding out the minimum cost function min_cost(i, num, cost, n) { // Base case if (n == 0) return cost[i]; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return 1e9; } // Case where we are not including the elements // present at num[i] let not_take = min_cost(i - 1, num, cost, n); // Case where we are including the elements // present at num[i]. let take = Number.MAX_VALUE; if (num[i] <= n) { // Calling recursion again for index i because of // the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i]); } // Returning the minimum of both i.e. // take and not take case return Math.min(take, not_take); } // Driver code let N = 7; let num = [1, 2, 10, 50]; let cost = [400, 750, 3250, 15000]; // Function call document.write(min_cost(3, num, cost, N)); // This code is contributed by Potta Lokesh </script> |
Output
2650
Time Complexity: O(2N)
Auxiliary Space: O(N)
Efficient Approach (Using Memoization):
We can use Dynamic Programming to store the answer for overlapping subproblems. We can store the result for the current index and the remaining number of elements in the DP matrix.
The states of DP can be represented as follows:
DP[current index][remaining elements]
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function for finding out the minimum costint min_cost(int i, int num[], int cost[], int n, vector<vector<int> >& dp){ // Base case if (n == 0) return 0; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return 1e9; } // If answer already stored return that if (dp[i][n] != -1) return dp[i][n]; // Case where we are not including the elements // present at num[i] int not_take = min_cost(i - 1, num, cost, n, dp); // Case where we are including the elements // present at num[i]. int take = INT_MAX; if (num[i] <= n) { // Calling recursion again for index i because of // the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i], dp); } // Returning the minimum of both i.e. // take and not take case return dp[i][n] = min(take, not_take);}// Driver codeint main(){ int N = 15; int len = 4; int num[len] = { 1, 2, 10, 50 }; int cost[len] = { 400, 750, 3250, 15000 }; // dp vector vector<vector<int> > dp(len, vector<int>(N + 1, -1)); // Function call cout << min_cost(len - 1, num, cost, N, dp); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.Scanner;class GFG { // Function for finding out the minimum cost static int min_cost(int i, int []num, int []cost, int n, int[][] dp) { // Base case if (n == 0) return 0; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return (int)1e9; } // If answer already stored return that if (dp[i][n] != -1) return dp[i][n]; // Case where we are not including the elements present at num[i] int not_take = min_cost(i - 1, num, cost, n, dp); // Case where we are including the elements present at num[i]. int take = Integer.MAX_VALUE; if (num[i] <= n) { // Calling recursion again for index i because of the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i], dp); } // Returning the minimum of both i.e. take and not take case return dp[i][n] = Math.min(take, not_take); } // Driver code public static void main(String[] args) { int N = 15; int len = 4; int[] num = new int[] { 1, 2, 10, 50 }; int[] cost = new int[] { 400, 750, 3250, 15000 }; // dp array int[][] dp = new int[len][N + 1]; for (int i = 0; i < len; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = -1; } } // Function call System.out.println(min_cost(3, num, cost, N, dp)); }}// This code is contributed by ajaymakvana. |
Python3
# Python code to implement the approach# Function for finding out the minimum costdef min_cost(i, num, cost, n, dp): # Base case if(n == 0): return 0 if(i == 0): if(num[0] <= n): return cost[0]*n else: return 10**9 # If answer already stored return that if(dp[i][n] != -1): return dp[i][n] # Case where we are not including the elements present at num[i] notTake = min_cost(i - 1, num, cost, n, dp) # Case where we are including the elements present at num[i]. take = 10**10 if(num[i] <= n): # Calling recursion again for index i because of the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i], dp) dp[i][n] = min(take,notTake) # Returning the minimum of both i.e. take and not take case return dp[i][n]# Driver codeif __name__ == "__main__": N = 15 length = 4 num = [1,2,10,50] cost = [400,750,3250,15000] # dp table dp = [] lis = [] for j in range(N+1): lis.append(-1) for i in range(length): dp.append(lis) # Function call print(min_cost(length-1,num,cost,N,dp)) # This code is contributed by ajaymakvana |
C#
using System;class GFG { static int min_cost(int i, int[] num, int[] cost, int n, int[, ] dp) { // Base case if (n == 0) return 0; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return (int)1e9; } // If answer already stored return that if (dp[i, n] != -1) return dp[i, n]; // Case where we are not including the elements // present at num[i] int not_take = min_cost(i - 1, num, cost, n, dp); // Case where we are including the elements // present at num[i]. int take = Int32.MaxValue; if (num[i] <= n) { // Calling recursion again for index i because // of the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i], dp); } // Returning the minimum of both i.e. // take and not take case return dp[i, n] = Math.Min(take, not_take); } // Driver's code public static void Main(string[] args) { int N = 15; int len = 4; int[] num = { 1, 2, 10, 50 }; int[] cost = { 400, 750, 3250, 15000 }; // dp vector int[, ] dp = new int[len, N + 1]; for (int i = 0; i < len; i++) for (int j = 0; j <= N; j++) dp[i, j] = -1; // vector<vector<int> > dp(len, vector<int>(N + 1, // -1)); // Function call Console.Write(min_cost(len - 1, num, cost, N, dp)); }}// This code is contributed by garg28harsh. |
Javascript
// Javascript code to implement the approach// Function for finding out the minimum costfunction min_cost(i,num,cost,n, dp){ // Base case if (n == 0) return 0; if (i == 0) { if (num[0] <= n) return cost[0] * n; else return 1e9; } // If answer already stored return that if (dp[i][n] != -1) return dp[i][n]; // Case where we are not including the elements // present at num[i] let not_take = min_cost(i - 1, num, cost, n, dp); // Case where we are including the elements // present at num[i]. let take = Number.MAX_VALUE; if (num[i] <= n) { // Calling recursion again for index i because of // the infinite supply available. take = cost[i] + min_cost(i, num, cost, n - num[i], dp); } // Returning the minimum of both i.e. // take and not take case return dp[i][n] = Math.min(take, not_take);}// Driver code let N = 15; let len = 4; let num = [ 1, 2, 10, 50 ]; let cost = [ 400, 750, 3250, 15000 ]; // dp vector let dp=[]; let abc = []; for(let i=0;i<N+1;i++) { abc.push(-1); } for(let i=0;i<len;i++) { dp.push(abc); } // Function call console.log(min_cost(len - 1, num, cost, N, dp)); // This code is contributed by ksam24000 |
Output
5150
Time Complexity: O(len*N), where len is the length of the array
Auxiliary Space: O(len*N)
Efficient Approach (Using Tabulation):
As we know that the memoization solution can be further optimized by using the tabulation method and we can reduce the auxiliary stack space taken by the memoization solution.
The states of DP remain the same as follows:
DP[current index][remaining elements]
Below is the implementation of the above approach:
C++
// A dynamic programming based solution for the problem#include <bits/stdc++.h>using namespace std;// Driver codeint main(){ int N = 15; int len = 4; int num[len] = { 1, 2, 10, 50 }; int cost[len] = { 400, 750, 3250, 15000 }; // dp vector initializing with 1e9 vector<vector<int> > dp(len, vector<int>(N + 1, 1e9)); // filling the dp vector for the base case for (int i = 0; i <= N; i++) { dp[0][i] = cost[0] * i; } // Build table dp[][] in bottom up manner for (int idx = 1; idx < len; idx++) { for (int j = 0; j <= N; j++) { // case when we are not including the element // present at num[i] int not_take = dp[idx - 1][j]; // Case where we are including the elements // present at num[i]. int take = INT_MAX; if (num[idx] <= j) { take = cost[idx] + dp[idx][j - num[idx]]; } // taking out the minimum from both dp[idx][j] = min(take, not_take); } } // our answer will be stored at dp[len-1][N] cout << dp[len - 1][N] << endl; return 0;}// This code is contributed by Geetesh Yadav |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class GFG { // Driver code public static void main(String[] args) { int N = 15; int len = 4; int num[] = { 1, 2, 10, 50 }; int cost[] = { 400, 750, 3250, 15000 }; // dp vector initializing with 1e9 int[][] dp = new int[len][N + 1]; for (int i = 0; i < len; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = Integer.MAX_VALUE; } } // filling the dp vector for the base case for (int i = 0; i <= N; i++) { dp[0][i] = cost[0] * i; } // Build table dp[][] in bottom up manner for (int idx = 1; idx < len; idx++) { for (int j = 0; j <= N; j++) { // case when we are not including the element present at num[i] int not_take = dp[idx - 1][j]; // Case where we are including the elements // present at num[i]. int take = Integer.MAX_VALUE; if (num[idx] <= j) { take = cost[idx] + dp[idx][j - num[idx]]; } // taking out the minimum from both dp[idx][j] = min(take, not_take); } } // our answer will be stored at dp[len-1][N] System.out.println(dp[len - 1][N]); } // function to return min value public static int min(int a, int b) { if (a < b) return a; return b; }}// This code is contributed by ajaymakvana. |
Python3
# python implementation# A dynamic programming based solution for the problemN = 15len = 4put = 10 ^ 9maxi = 9223372036854775807num = [1, 2, 10, 50]cost = [400, 750, 3250, 15000]# dp vector initializing with 1e9dp = [[put]*(N+1) for i in range(len)]# filling the dp vector for the base case# for ( i = 0 i <= N i++)for i in range(0, N+1): dp[0][i] = cost[0] * i # Build table dp[][] in bottom up manner# for ( idx = 1 idx < len idx++)for idx in range(1, len): # for ( j = 0 j <= N j++) for j in range(0, N+1): # case when we are not including the element # present at num[i] not_take = dp[idx - 1][j] # Case where we are including the elements # present at num[i]. take = maxi if (num[idx] <= j): take = cost[idx] + dp[idx][j - num[idx]] # taking out the minimum from both dp[idx][j] = min(take, not_take) # our answer will be stored at dp[len-1][N]print(dp[len - 1][N])# This code is contributed by ksam24000 |
C#
// C# code for the above approachusing System;public class GFG { static public void Main() { int N = 15; int len = 4; int[] num = { 1, 2, 10, 50 }; int[] cost = { 400, 750, 3250, 15000 }; // dp vector initializing with 1e9 int[, ] dp = new int[len, N + 1]; for (int i = 0; i < len; i++) { for (int j = 0; j <= N; j++) { dp[i, j] = Int32.MaxValue; } } // filling the dp vector for the base case for (int i = 0; i <= N; i++) { dp[0, i] = cost[0] * i; } // Build table dp[][] in bottom up manner for (int idx = 1; idx < len; idx++) { for (int j = 0; j <= N; j++) { // case when we are not including the // element present at num[i] int not_take = dp[idx - 1, j]; // Case where we are including the elements // present at num[i]. int take = Int32.MaxValue; if (num[idx] <= j) { take = cost[idx] + dp[idx, j - num[idx]]; } // taking out the minimum from both dp[idx, j] = min(take, not_take); } } // our answer will be stored at dp[len-1][N] Console.WriteLine(dp[len - 1, N]); } // function to return min value public static int min(int a, int b) { if (a < b) return a; return b; }}// This code is contributed by lokeshmvs21. |
Javascript
// Js code for the above approach // function to return min value function min(a, b) { if (a < b) return a; return b; }function makeArray(d1, d2) { var arr = new Array(d1), i, l; for(i = 0, l = d2; i < l; i++) { arr[i] = new Array(d1); } return arr;}// Driver code let N = 15; let len = 4; let num = [ 1, 2, 10, 50 ]; let cost= [ 400, 750, 3250, 15000 ]; // dp vector initializing with 1e9 let dp = makeArray(len,N+1); for (let i = 0; i < len; i++) { for (let j = 0; j <= N; j++) { dp[i][j] = Number.MAX_SAFE_INTEGER; } } // filling the dp vector for the base case for (let i = 0; i <= N; i++) { dp[0][i] = cost[0] * i; } // Build table dp[][] in bottom up manner for (let idx = 1; idx < len; idx++) { for (let j = 0; j <= N; j++) { // case when we are not including the element present at num[i] let not_take = dp[idx - 1][j]; // Case where we are including the elements // present at num[i]. let take = Number.MAX_SAFE_INTEGER; if (num[idx] <= j) { take = cost[idx] + dp[idx][j - num[idx]]; } // taking out the minimum from both dp[idx][j] = Math.min(take, not_take); } } // our answer will be stored at dp[len-1][N] console.log((dp[len - 1][N]));// This code is contributed by ksam24000. |
Output
5150
Time Complexity: O(len*N), where len is the length of the array
Auxiliary Space: O(len*N)
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!
