Maximize the Profit by Selling at-most M Products
The problem is to maximize profit by selling at most M products. You are given an array of prices, where each element represents the price of a product. The goal is to select at most M products from the array in such a way that the total profit obtained from selling these products is maximized.
Example
Input
costPrice = { 2, 3, 1, 5, 4, 2 }; sellingPrice = { 6, 8, 5, 10, 9, 7 };
Output
20
Explanation: Here we have two lists that contain cost prices CP[] and selling prices SP[] of products respectively. The task is to maximize the profit by selling at-most ‘M’ products it can be solved using a greedy algorithm and dynamic programming.
Approach: Greedy Algorithm
Example 1
In the above code, we have to sell the fruits at max price. The program takes the cost prices of fruits (costPrice) and their respective selling prices (sellingPrice) as inputs. In the main method, we set the values of N and M to 6 and 4, respectively. The costPrice and sellingPrice arrays are initialized with the corresponding values for each fruit. Finally, the maximizeProfit method is called with the provided inputs, and the result, which is the maximum profit, is printed.
FileName: FruitPro.java
import java.util.*; class FruitPro { // Function to find profit static int maximizeProfit(int N, int M, int[] costPrice, int[] sellingPrice) { Integer[] profit = new Integer[N]; // Calculating profit for each fruit for (int i = 0; i < N; i++) profit[i] = sellingPrice[i] - costPrice[i]; // Sort the profit array in descending order Arrays.sort(profit, Collections.reverseOrder()); // Variable to calculate total profit int totalProfit = 0; // Check for the best M profits for (int i = 0; i < M; i++) { if (profit[i] > 0) totalProfit += profit[i]; else break; } return totalProfit; } // Driver Code public static void main(String args[]) { int N = 6, M = 4; int[] costPrice = { 2, 3, 1, 5, 4, 2 }; int[] sellingPrice = { 6, 8, 5, 10, 9, 7 }; int maxProfit = maximizeProfit(N, M, costPrice, sellingPrice); System.out.println("Maximum Profit: $" + maxProfit); } }
Output
Maximum Profit: $20
Complexity
The given code has a time complexity of O(N log N) and a space complexity of O(N).
The time complexity of O(N log N) arises from the sorting operation performed on the profit array using Arrays.sort(). As the number of fruits, N, increases, the time required to sort the array grows in a logarithmic manner.
The space complexity of O(N) is due to the additional array used to store the calculated profits. It grows linearly with the number of fruits, N. The rest of the variables and operations in the code have constant space requirements and do not contribute significantly to the overall space complexity.
In summary, the code has a time complexity of O(N log N) and a space complexity of O(N), with N representing the number of fruits.
Approach: Dynamic Programming
Example 2
In the above code, we have two arrays: costPrices and sellingPrices. The costPrices array contains the cost price of each product, and the sellingPrices array contains the corresponding selling price of each product.In the main method, we have added sample arrays for costPrices and sellingPrices, and set M to 3. The code calculates the maximum profit by considering the cost and selling prices using the maximizeProfit function, and then prints the result.
FileName: MaximizeProfit.java
public class MaximizeProfit { public static int maximizeProfit(int[] costPrices, int[] sellingPrices, int M) { int n = costPrices.length; int[][] dp = new int[n + 1][M + 1]; // Fill the dynamic programming table for (int i = 1; i <= n; i++) { for (int j = 1; j <= M; j++) { if (j >= i) { // If the number of products to select is greater than or equal to the current product index, // we can choose to include the current product or exclude it dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - i] + (sellingPrices[i - 1] - costPrices[i - 1])); } else { // If the number of products to select is less than the current product index, // we cannot include the current product dp[i][j] = dp[i - 1][j]; } } } return dp[n][M]; } public static void main(String[] args) { int[] costPrices = {8, 20, 15, 40, 30}; int[] sellingPrices = {10, 30, 25, 50, 40}; int M = 3; int maxProfit = maximizeProfit(costPrices, sellingPrices, M); System.out.println("Maximum Profit: " + maxProfit); } }
Output
Maximum Profit: 12
Complexity
The time complexity of the code is O(n * M), and the space complexity is O(n * M), where n is the number of products and M is the maximum number of products to select. Both complexities are directly proportional to the product of n and M.