Given the cost[] and profit[] of N stocks and K tickets, the task is to find the maximum total profit that can be obtained from M initial amount of money using K tickets.
Note: A ticket can be used to reduce the cost of any stock to half of the original price and on a particular stock, a ticket can be used only once.
Examples:
Input: N = 3, cost[] = {2, 4, 5}, profit[] = {20, 17, 15}, K = 1, M = 4
Output: 37
Explanation: The most optimal case is when we take the 1st stock at regular cost and use a ticket for 2nd item. Total amount of money spent = (2 + (4 / 2)) = 4 ≤ M. Total Profit obtained is = 20 + 17 = 37Input: N = 3, cost[] = {4, 4, 3}, profit[] = {12, 14, 7}, K = 2, M = 5
Output: 26
Explanation: The most optimal case is when we take the 1st stock using the 1st ticket and the 2nd item using the 2nd ticket. Total amount of money spent = ((4 / 2) + (4 / 2)) = 4 ≤ M. Total Profit obtained is = 12 +14 = 26
Naive Approach: Implement the idea below to solve the problem:
It is always beneficial to use the maximum number of tickets because it will reduce the price of the stock. For each item there are 3 choices:
- Don’t consider the current stock.
- Take the current but don’t use the ticket.
- Take the current and use the ticket.
Steps were taken to solve the problem:
- Initialise the integer variable Ans for storing maximum profit earned.
- To consider all subsets of items, for a given element we have 3 choices:
- Don’t take the current Stock, then the current amount left will be M, Ans remain the same.
- If possible(M ≥ cost[i]), take the current stock and add its profit value to the Ans then the current money left will be M – cost[i].
- If the ticket is used, add its profit value to the Ans, then the current money left will be M – cost[i]/2.
- Return maximum Ans of the above three possible cases.
Below is the code implementation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate Maximum Profitint maxProfit(int i, int N, int cost[], int profit[], int K, int M){ if (i == N) { return 0; } // Don't take the current stock int ans1 = maxProfit(i + 1, N, cost, profit, K, M); int ans2 = INT_MIN; int ans3 = INT_MIN; // If current stock can be taken // take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // If current stock can be taken // with ticket take it if (K > 0) { int newcost = cost[i] / 2; if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // Returning maximum profit earned return max(ans1, max(ans2, ans3));}// Drivers codeint main(){ int cost[] = { 2, 4, 5 }; int profit[] = { 20, 17, 15 }; int N = sizeof(cost) / sizeof(cost[0]); int K = 1, M = 4; // Function call cout << maxProfit(0, N, cost, profit, K, M); return 0;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Function to calculate Maximum profit static int maxProfit(int i, int N, int[] cost, int[] profit, int K, int M) { if (i == N) { return 0; } // Don't take the current stock int ans1 = maxProfit(i + 1, N, cost, profit, K, M); int ans2 = Integer.MIN_VALUE; int ans3 = Integer.MIN_VALUE; // If current stock can be taken take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // If current stock can be taken with ticket take it if (K > 0) { int newcost = cost[i] / 2; if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // Returning maximum profit earned return Math.max(ans1, Math.max(ans2, ans3)); } public static void main(String[] args) { int[] cost = { 2, 4, 5 }; int[] profit = { 20, 17, 15 }; int N = cost.length; int K = 1, M = 4; // Function call System.out.print( maxProfit(0, N, cost, profit, K, M)); }}// This code is contributed by lokesh. |
Python3
# Python code for the above approachimport sys# Function to calculate Maximum Profitdef maxProfit(i,N,cost,profit,K,M): if(i==N): return 0 # Don't take the current stock ans1=maxProfit(i+1,N,cost,profit,K,M) ans2 = -1*sys.maxsize ans3 = -1*sys.maxsize # If current stock can be taken # take it if(M >= cost[i]): ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]) # If current stock can be taken # with ticket take it if(K > 0): newcost = cost[i]//2 if(M >= newcost): ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost) # Returning maximum profit earned return max(ans1, max(ans2, ans3)) # Driver codecost = [2,4,5]profit = [20,17,15]N = len(cost)K = 1M = 4# Function callprint(maxProfit(0, N, cost, profit, K, M))# This code is contributed by Pushpesh Raj. |
C#
// C# implementationusing System;public class GFG { // Function to calculate Maximum Profit public static int maxProfit(int i, int N, int[] cost, int[] profit, int K, int M) { if (i == N) { return 0; } // Don't take the current stock int ans1 = maxProfit(i + 1, N, cost, profit, K, M); int ans2 = Int32.MinValue; int ans3 = Int32.MinValue; // If current stock can be taken // take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // If current stock can be taken // with ticket take it if (K > 0) { int newcost = (int)(cost[i] / 2); if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // Returning maximum profit earned return Math.Max(ans1, Math.Max(ans2, ans3)); } static public void Main() { int[] cost = { 2, 4, 5 }; int[] profit = { 20, 17, 15 }; int N = cost.Length; int K = 1, M = 4; // Function call Console.WriteLine( maxProfit(0, N, cost, profit, K, M)); }}// This code is contributed by ksam24000. |
Javascript
// javascript code for the above approach// Function to calculate Maximum Profitfunction maxProfit(i, N, cost,profit, K, M){ if (i == N) { return 0; } // Don't take the current stock let ans1 = maxProfit(i + 1, N, cost, profit, K, M); let ans2 = Number.MIN_VALUE; let ans3 = Number.MIN_VALUE; // If current stock can be taken // take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // If current stock can be taken // with ticket take it if (K > 0) { let newcost = cost[i] / 2; if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // Returning maximum profit earned return Math.max(ans1, Math.max(ans2, ans3));}// Drivers code let cost = [ 2, 4, 5 ]; let profit = [ 20, 17, 15 ]; let N = cost.length, K = 1, M = 4; // Function call console.log(maxProfit(0, N, cost, profit, K, M));// This code is contributed by garg28harsh. |
Output
37
Time Complexity = O(3N)
Auxiliary Space = O(1)
Efficient Approach using Dynamic Programming:
The above approach has overlapping subproblems as can be seem below. Say:
M = 5, N = 3, K = 2, Cost[] = {4, 4, 3}, Profit[]={ 12, 14, 7}
Let X(M, 0, K) represent the given state that M initial money and K tickets and at index 0:
- Left move – 1st case – Don’t take current element
- Down move – 2nd case – Take the current element
- Right move – 3rd case – Take the current element with Ticket.
The recursion tree for the test case
So we can use the concept of dynamic programming.
Follow the steps mentioned below to implement the idea:
- Initialize a 3D array (say dp[][][]) to store the value of each state as shown above.
- Now use the same recursion as the previous approach.
- To reduce the calculation, if a state which is already calculated is encountered, return the maximum profit for that state.
- The value stored at the state (M, 0, K) is the required answer.
Below is the implementation of the efficient approach.
C++
// C++ implementation of the code#include <bits/stdc++.h>using namespace std;// Initialize 3D dpint dp[1001][501][11];// Function to calculate Maximum profit// earnedint maxProfit(int i, int N, int cost[], int profit[], int K, int M){ if (i == N) { return 0; } // State of dp already calculated or not if (dp[M][i][K] != -1) { return dp[M][i][K]; } // Don't take the current stock int ans1 = maxProfit(i + 1, N, cost, profit, K, M); int ans2 = INT_MIN; int ans3 = INT_MIN; // if current stock can be taken take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // if current stock can be taken with // ticket take it if (K > 0) { int newcost = cost[i] / 2; if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // store the current dp state and return // the ans return dp[M][i][K] = max(ans1, max(ans2, ans3));}int main(){ // Number of stocks int N = 3; int cost[3] = { 2, 4, 5 }; int profit[3] = { 20, 17, 15 }; // Tickets to use int K = 1; // Current Money int M = 4; // Setting all values of dp array to -1 memset(dp, -1, sizeof(dp)); // Function call cout << maxProfit(0, N, cost, profit, K, M); return 0;} |
Java
// Java implementation of the codeimport java.util.*;public class GFG { // Initialize 3D dp static int dp[][][] = new int[1001][501][11]; // Function to calculate Maximum profit // earned public static int maxProfit(int i, int N, int cost[], int profit[], int K, int M) { if (i == N) { return 0; } // State of dp already calculated or not if (dp[M][i][K] != -1) { return dp[M][i][K]; } // Don't take the current stock int ans1 = maxProfit(i + 1, N, cost, profit, K, M); int ans2 = Integer.MIN_VALUE; int ans3 = Integer.MIN_VALUE; // if current stock can be taken take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // if current stock can be taken with // ticket take it if (K > 0) { int newcost = cost[i] / 2; if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // store the current dp state and return // the ans return dp[M][i][K] = Math.max(ans1, Math.max(ans2, ans3)); } public static void main(String args[]) { // Number of stocks int N = 3; int cost[] = { 2, 4, 5 }; int profit[] = { 20, 17, 15 }; // Tickets to use int K = 1; // Current Money int M = 4; // Setting all values of dp array to -1 for (int i = 0; i < 1001; i++) { for (int j = 0; j < 501; j++) { for (int k = 0; k < 11; k++) { dp[i][j][k] = -1; } } } // Function call System.out.println( maxProfit(0, N, cost, profit, K, M)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python implementation of the code# Initialize 3D dpdp = [[[-1 for k in range(11)] for j in range(501)] for i in range(1001)]# Function to calculate Maximum profit# earneddef maxProfit(i, N, cost, profit, K, M): if i == N: return 0 # State of dp already calculated or not if dp[M][i][K] != -1: return dp[M][i][K] # Don't take the current stock ans1 = maxProfit(i + 1, N, cost, profit, K, M) ans2 = float('-inf') ans3 = float('-inf') # if current stock can be taken take it if M >= cost[i]: ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]) # if current stock can be taken with # ticket take it if K > 0: newcost = cost[i] // 2 if M >= newcost: ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost) # store the current dp state and return # the ans dp[M][i][K] = max(ans1, max(ans2, ans3)) return dp[M][i][K]# Number of stocksN = 3cost = [2, 4, 5]profit = [20, 17, 15]# Tickets to useK = 1# Current MoneyM = 4# Function callprint(maxProfit(0, N, cost, profit, K, M))# This code is contributed by Harshad |
C#
// C# implementation of the codeusing System;using System.Collections;using System.Collections.Generic;public class GFG { // Initialize 3D dp static int[, , ] dp = new int[1001, 501, 11]; // Function to calculate Maximum profit // earned public static int maxProfit(int i, int N, int[] cost, int[] profit, int K, int M) { if (i == N) { return 0; } // State of dp already calculated or not if (dp[M, i, K] != -1) { return dp[M, i, K]; } // Don't take the current stock int ans1 = maxProfit(i + 1, N, cost, profit, K, M); int ans2 = Int32.MinValue; int ans3 = Int32.MinValue; // if current stock can be taken take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // if current stock can be taken with // ticket take it if (K > 0) { int newcost = cost[i] / 2; if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // store the current dp state and return // the ans return dp[M, i, K] = Math.Max(ans1, Math.Max(ans2, ans3)); } public static void Main(string[] args) { // Number of stocks int N = 3; int[] cost = { 2, 4, 5 }; int[] profit = { 20, 17, 15 }; // Tickets to use int K = 1; // Current Money int M = 4; // Setting all values of dp array to -1 for (int i = 0; i < 1001; i++) { for (int j = 0; j < 501; j++) { for (int k = 0; k < 11; k++) { dp[i, j, k] = -1; } } } // Function call Console.WriteLine( maxProfit(0, N, cost, profit, K, M)); }}// This code is contributed by Karandeep1234 |
Javascript
// Javascript implementation of the code// Initialize 3D dplet dp = Array(1001).fill().map(e => Array(501).fill().map(e => Array(11).fill(-1).map(e => e)));// Function to calculate Maximum profit// earnedfunction maxProfit(i, N, cost, profit, K, M){ if (i == N) { return 0; } // State of dp already calculated or not if (dp[M][i][K] != -1) { return dp[M][i][K]; } // Don't take the current stock let ans1 = maxProfit(i + 1, N, cost, profit, K, M); let ans2 = Number.MIN_SAFE_INTEGER; let ans3 = Number.MIN_SAFE_INTEGER; // if current stock can be taken take it if (M >= cost[i]) { ans2 = profit[i] + maxProfit(i + 1, N, cost, profit, K, M - cost[i]); } // if current stock can be taken with // ticket take it if (K > 0) { let newcost = Math.floor(cost[i] / 2); if (M >= newcost) { ans3 = profit[i] + maxProfit(i + 1, N, cost, profit, K - 1, M - newcost); } } // store the current dp state and return // the ans return dp[M][i][K] = Math.max(ans1, Math.max(ans2, ans3));} // Number of stocks let N = 3; let cost = [ 2, 4, 5 ]; let profit = [ 20, 17, 15 ]; // Tickets to use let K = 1; // Current Money let M = 4; // Setting all values of dp array to -1 for (let i = 0; i < 1001; i++) { for (let j = 0; j < 501; j++) { for (let k = 0; k < 11; k++) { dp[i][j][k] = -1; } } } // Function call console.log(maxProfit(0, N, cost, profit, K, M));// This code is contributed by Utkarsh |
Output
37
Time Complexity: O(N*M*K)
Auxiliary Space: O(N*M*K)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Implementation :
C++
#include <bits/stdc++.h>using namespace std;int maxProfit(int N, int K, int M, int cost[], int profit[]) { int dp[M+1][K+1][N+1]; // dp[M][K][i] stores max profit for M money, K tickets remaining, and ith stock // Initialize base cases for (int i = 0; i <= M; i++) { for (int j = 0; j <= K; j++) { for (int k = 0; k <= N; k++) { if (i == 0 || j == 0) { dp[i][j][k] = 0; } else { dp[i][j][k] = -1; } } } } // Perform bottom-up DP for (int i = N-1; i >= 0; i--) { for (int j = 0; j <= K; j++) { for (int k = 0; k <= M; k++) { int ans1 = dp[k][j][i+1]; // Don't take the current stock int ans2 = INT_MIN; int ans3 = INT_MIN; // if current stock can be taken, take it if (k >= cost[i]) { ans2 = profit[i] + dp[k-cost[i]][j][i+1]; } // if current stock can be purchased with a ticket, take it using the ticket if (j > 0 && cost[i]/2 <= k) { ans3 = profit[i] + dp[k-cost[i]/2][j-1][i+1]; } dp[k][j][i] = max(ans1, max(ans2, ans3)); } } } // final answer return dp[M][K][0];}// Driver Code int main() { int N = 3; int cost[3] = {2, 4, 5}; int profit[3] = {20, 17, 15}; int K = 1; int M = 4; // function call cout << maxProfit(N, K, M, cost, profit) << endl; return 0;}// -- by bhardwajji |
Java
import java.io.*;class GFG { static int maxProfit(int N, int K, int M, int cost[], int profit[]) { int[][][] dp = new int[M + 1][K + 1][N + 1]; // dp[M][K][i] stores max profit // for M money, K tickets // remaining, and ith stock // Initialize base cases for (int i = 0; i <= M; i++) { for (int j = 0; j <= K; j++) { for (int k = 0; k <= N; k++) { if (i == 0 || j == 0) { dp[i][j][k] = 0; } else { dp[i][j][k] = -1; } } } } // Perform bottom-up DP for (int i = N - 1; i >= 0; i--) { for (int j = 0; j <= K; j++) { for (int k = 0; k <= M; k++) { int ans1 = dp[k][j][i + 1]; // Don't take the // current stock int ans2 = Integer.MIN_VALUE; int ans3 = Integer.MIN_VALUE; // if current stock can be taken, take // it if (k >= cost[i]) { ans2 = profit[i] + dp[k - cost[i]][j][i + 1]; } // if current stock can be purchased // with a ticket, take it using the // ticket if (j > 0 && cost[i] / 2 <= k) { ans3 = profit[i] + dp[k - cost[i] / 2][j - 1] [i + 1]; } dp[k][j][i] = Math.max( ans1, Math.max(ans2, ans3)); } } } // final answer return dp[M][K][0]; } public static void main(String[] args) { int N = 3; int cost[] = { 2, 4, 5 }; int profit[] = { 20, 17, 15 }; int K = 1; int M = 4; // function call System.out.println( maxProfit(N, K, M, cost, profit)); }} |
C#
using System;public class GFG { public static int MaxProfit(int N, int K, int M, int[] cost, int[] profit) { int[, , ] dp = new int[M + 1, K + 1, N + 1]; // dp[M, K, i] stores max // profit for M money, K // tickets remaining, and ith // stock // Initialize base cases for (int i = 0; i <= M; i++) { for (int j = 0; j <= K; j++) { for (int k = 0; k <= N; k++) { if (i == 0 || j == 0) { dp[i, j, k] = 0; } else { dp[i, j, k] = -1; } } } } // Perform bottom-up DP for (int i = N - 1; i >= 0; i--) { for (int j = 0; j <= K; j++) { for (int k = 0; k <= M; k++) { int ans1 = dp[k, j, i + 1]; // Don't take the // current stock int ans2 = int.MinValue; int ans3 = int.MinValue; // if current stock can be taken, take // it if (k >= cost[i]) { ans2 = profit[i] + dp[k - cost[i], j, i + 1]; } // if current stock can be purchased // with a ticket, take it using the // ticket if (j > 0 && cost[i] / 2 <= k) { ans3 = profit[i] + dp[k - cost[i] / 2, j - 1, i + 1]; } dp[k, j, i] = Math.Max( ans1, Math.Max(ans2, ans3)); } } } // final answer return dp[M, K, 0]; } public static void Main(string[] args) { int N = 3; int[] cost = { 2, 4, 5 }; int[] profit = { 20, 17, 15 }; int K = 1; int M = 4; // function call Console.WriteLine(MaxProfit(N, K, M, cost, profit)); }} |
Output
37
Time Complexity: O(N*M*K)
Auxiliary Space: O(N*M*K)
Related articles:
- Introduction to Arrays – Data Structure and Algorithm Tutorials
- Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
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!
