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