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 Profit 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 = 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 code int 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 approach import 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 approach import sys Â
# Function to calculate Maximum Profit def 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 code cost = [ 2 , 4 , 5 ] profit = [ 20 , 17 , 15 ] N = len (cost) K = 1 M = 4 Â
# Function call print (maxProfit( 0 , N, cost, profit, K, M)) Â
# This code is contributed by Pushpesh Raj. |
C#
// C# implementation using 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 Profit function 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. |
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 dp int dp[1001][501][11]; Â
// Function to calculate Maximum profit // earned 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 = 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 code import 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 dp dp = [[[ - 1 for k in range ( 11 )] for j in range ( 501 )] for i in range ( 1001 )] Â
# Function to calculate Maximum profit # earned def 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 stocks N = 3 cost = [ 2 , 4 , 5 ] profit = [ 20 , 17 , 15 ] Â
# Tickets to use K = 1 Â
# Current Money M = 4 Â
# Function call print (maxProfit( 0 , N, cost, profit, K, M)) Â
# This code is contributed by Harshad |
C#
// C# implementation of the code using 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 dp let dp = Array(1001).fill().map(e => Array(501).fill().map(e => Array(11).fill(-1).map(e => e))); Â
// Function to calculate Maximum profit // earned function 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 |
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));     } } |
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
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!