Maximum profit using M money and reducing half price of at most K stocks

0 0 15 minutes read

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 = 37

Input: 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.

Output

Time Complexity = O(3^N)
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

Output

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

Time Complexity: O(N*M*K)
Auxiliary Space: O(N*M*K)

Related articles:

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