Dynamic Programming | High-effort vs. Low-effort Tasks Problem
You are given n days and for each day (di) you could either perform a high effort tasks (hi) or a low effort tasks (li) or no task with the constraint that you can choose high-effort tasks only if you choose no task on the previous day. Write a program to find the maximum amount of tasks you can perform within these n days.
Examples:
No. of days (n) = 5
Day L.E. H.E
1 1 3
2 5 6
3 4 8
4 5 7
5 3 6Maximum amount of tasks = 3 + 5 + 4 + 5 + 3 = 20
Method 1:
Optimal Substructure: To find the maximum amount of tasks done till i’th day, we need to compare 2 choices:
- Go for high-effort tasks on that day, then find the maximum amount of tasks done till (i – 2) th day.
- Go for low effort task on that day and find the maximum amount of tasks done till (i – 1) th day.
Let high [1…n] be the input array for high effort task amount on i’th day and low [1…n] be the input array for low effort task amount on ith day.
Let max_task (high [], low [], i) be the function that returns maximum amount of task done till ith day, so it will return max(high[i] + max_task(high, low, (i – 2)), low [i] + max_task (high, low, (i – 1)))
Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.
Overlapping Subproblems: Following is a simple recursive implementation of the High-effort vs. Low-effort task problem.
The implementation simply follows the recursive structure mentioned above. So, High-effort vs. Low-effort Task Problem has both properties of a dynamic programming problem.
Below is the implementation of the above approach:
C++
// A naive recursive C++ program to find maximum // tasks. #include <iostream> using namespace std; // Returns the maximum among the 2 numbers int max( int x, int y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n int maxTasks( int high[], int low[], int n) { // If n is less than equal to 0, then no // solution exists if (n <= 0) return 0; /* Determines which task to choose on day n, then returns the maximum till that day */ return max(high[n - 1] + maxTasks(high, low, (n - 2)), low[n - 1] + maxTasks(high, low, (n - 1))); } // Driver code int main() { int n = 5; int high[] = {3, 6, 8, 7, 6}; int low[] = {1, 5, 4, 5, 3}; cout << maxTasks(high, low, n); return 0; } // This code is contributed by Shubhamsingh10 |
C
// A naive recursive C program to find maximum // tasks. #include<stdio.h> // Returns the maximum among the 2 numbers int max( int x, int y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n int maxTasks( int high[], int low[], int n) { // If n is less than equal to 0, then no // solution exists if (n <= 0) return 0; /* Determines which task to choose on day n, then returns the maximum till that day */ return max(high[n-1] + maxTasks(high, low, (n-2)), low[n-1] + maxTasks(high, low, (n-1))); } // Driver program to test above function int main() { int n = 5; int high[] = {3, 6, 8, 7, 6}; int low[] = {1, 5, 4, 5, 3}; printf ( "%d\n" , maxTasks(high, low, n)); return 0; } |
Java
// A naive recursive Java program // to find maximum tasks. import java.io.*; class GFG{ // Returns maximum amount of task // that can be done till day n static int maxTasks( int high[], int low[], int n) { // If n is less than equal to 0, // then no solution exists if (n <= 0 ) return 0 ; /* Determines which task to choose on day n, then returns the maximum till that day */ return Math.max(high[n - 1 ] + maxTasks(high, low, (n - 2 )), low[n - 1 ] + maxTasks(high, low, (n - 1 ))); } // Driver code public static void main(String []args) { int n = 5 ; int high[] = { 3 , 6 , 8 , 7 , 6 }; int low[] = { 1 , 5 , 4 , 5 , 3 }; System.out.println( maxTasks(high, low, n)); } } // This code is contributed by Ita_c. |
Python3
# A naive recursive Python3 program to # find maximum tasks. # Returns maximum amount of task # that can be done till day n def maxTasks(high, low, n) : # If n is less than equal to 0, # then no solution exists if (n < = 0 ) : return 0 # Determines which task to choose on day n, # then returns the maximum till that day return max (high[n - 1 ] + maxTasks(high, low, (n - 2 )), low[n - 1 ] + maxTasks(high, low, (n - 1 ))); # Driver Code if __name__ = = "__main__" : n = 5 ; high = [ 3 , 6 , 8 , 7 , 6 ] low = [ 1 , 5 , 4 , 5 , 3 ] print (maxTasks(high, low, n)); # This code is contributed by Ryuga |
C#
// A naive recursive C# program // to find maximum tasks. using System; class GFG { // Returns maximum amount of task // that can be done till day n static int maxTasks( int [] high, int [] low, int n) { // If n is less than equal to 0, // then no solution exists if (n <= 0) return 0; /* Determines which task to choose on day n, then returns the maximum till that day */ return Math.Max(high[n - 1] + maxTasks(high, low, (n - 2)), low[n - 1] + maxTasks(high, low, (n - 1))); } // Driver code public static void Main() { int n = 5; int [] high = {3, 6, 8, 7, 6}; int [] low = {1, 5, 4, 5, 3}; Console.Write( maxTasks(high, low, n)); } } // This code is contributed by Ita_c. |
Javascript
<script> // A naive recursive Java program // to find maximum tasks. // Returns maximum amount of task // that can be done till day n function maxTasks(high, low, n) { // If n is less than equal to 0, // then no solution exists if (n <= 0) return 0; /* Determines which task to choose on day n, then returns the maximum till that day */ return Math.max(high[n - 1] + maxTasks(high, low, (n - 2)), low[n - 1] + maxTasks(high, low, (n - 1))); } // Driver code let n = 5; let high = [3, 6, 8, 7, 6]; let low = [1, 5, 4, 5, 3]; document.write( maxTasks(high, low, n));; </script> |
PHP
<?php // A naive recursive PHP program to find maximum // tasks. // Returns maximum amount of task that can be // done till day n function maxTasks( $high , $low , $n ) { // If n is less than equal to 0, then no // solution exists if ( $n <= 0) return 0; /* Determines which task to choose on day n, then returns the maximum till that day */ return max( $high [ $n - 1] + maxTasks( $high , $low , ( $n - 2)), $low [ $n - 1] + maxTasks( $high , $low , ( $n - 1))); } // Driver Code $n = 5; $high = array (3, 6, 8, 7, 6); $low = array (1, 5, 4, 5, 3); print (maxTasks( $high , $low , $n )); // This code is contributed by mits ?> |
20
It should be noted that the above function computes the same subproblems again and again.
Therefore, this problem has Overlapping Subproblems Property. So the High-effort vs. Low-effort Task Problem has both the properties of a dynamic programming problem.
Method 2: Dynamic Programming Solution
C++
// A DP based C++ program to find maximum tasks. #include <iostream> using namespace std; // Returns the maximum among the 2 numbers int max( int x, int y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n int maxTasks( int high[], int low[], int n) { // An array task_dp that stores the maximum // task done int task_dp[n+1]; // If n = 0, no solution exists task_dp[0] = 0; // If n = 1, high effort task on that day will // be the solution task_dp[1] = high[0]; // Fill the entire array determining which // task to choose on day i for ( int i = 2; i <= n; i++) task_dp[i] = max(high[i-1] + task_dp[i-2], low[i-1] + task_dp[i-1]); return task_dp[n]; } // Driver program to test above function int main() { int n = 5; int high[] = {3, 6, 8, 7, 6}; int low[] = {1, 5, 4, 5, 3}; cout << maxTasks(high, low, n); return 0; } // This code is contributed by shivanisinghss2110 |
C
// A DP based C++ program to find maximum tasks. #include<stdio.h> // Returns the maximum among the 2 numbers int max( int x, int y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n int maxTasks( int high[], int low[], int n) { // An array task_dp that stores the maximum // task done int task_dp[n+1]; // If n = 0, no solution exists task_dp[0] = 0; // If n = 1, high effort task on that day will // be the solution task_dp[1] = high[0]; // Fill the entire array determining which // task to choose on day i for ( int i = 2; i <= n; i++) task_dp[i] = max(high[i-1] + task_dp[i-2], low[i-1] + task_dp[i-1]); return task_dp[n]; } // Driver program to test above function int main() { int n = 5; int high[] = {3, 6, 8, 7, 6}; int low[] = {1, 5, 4, 5, 3}; printf ( "%d" , maxTasks(high, low, n)); return 0; } |
Java
// A DP based Java program to find maximum tasks. import java.io.*; class GFG { // Returns the maximum among the 2 numbers static int max( int x, int y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n static int maxTasks( int [] high, int [] low, int n) { // An array task_dp that stores the maximum // task done int [] task_dp = new int [n + 1 ]; // If n = 0, no solution exists task_dp[ 0 ] = 0 ; // If n = 1, high effort task on that day will // be the solution task_dp[ 1 ] = high[ 0 ]; // Fill the entire array determining which // task to choose on day i for ( int i = 2 ; i <= n; i++) task_dp[i] = Math.max(high[i - 1 ] + task_dp[i - 2 ], low[i - 1 ] + task_dp[i - 1 ]); return task_dp[n]; } // Driver code public static void main(String[] args) { int n = 5 ; int [] high = { 3 , 6 , 8 , 7 , 6 }; int [] low = { 1 , 5 , 4 , 5 , 3 }; System.out.println(maxTasks(high, low, n)); } } // This code is contributed by Code_Mech. |
Python3
# A DP based Python3 program to find maximum tasks. # Returns the maximum among the 2 numbers def max1(x, y): return x if (x > y) else y; # Returns maximum amount of task # that can be done till day n def maxTasks(high, low, n): # An array task_dp that stores # the maximum task done task_dp = [ 0 ] * (n + 1 ); # If n = 0, no solution exists task_dp[ 0 ] = 0 ; # If n = 1, high effort task # on that day will be the solution task_dp[ 1 ] = high[ 0 ]; # Fill the entire array determining # which task to choose on day i for i in range ( 2 , n + 1 ): task_dp[i] = max (high[i - 1 ] + task_dp[i - 2 ], low[i - 1 ] + task_dp[i - 1 ]); return task_dp[n]; # Driver code n = 5 ; high = [ 3 , 6 , 8 , 7 , 6 ]; low = [ 1 , 5 , 4 , 5 , 3 ]; print (maxTasks(high, low, n)); # This code is contributed by mits |
C#
// A DP based C# program to find maximum tasks. using System; class GFG { // Returns the maximum among the 2 numbers static int max( int x, int y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n static int maxTasks( int []high, int []low, int n) { // An array task_dp that stores the maximum // task done int [] task_dp = new int [n + 1]; // If n = 0, no solution exists task_dp[0] = 0; // If n = 1, high effort task on that day will // be the solution task_dp[1] = high[0]; // Fill the entire array determining which // task to choose on day i for ( int i = 2; i <= n; i++) task_dp[i] = max(high[i - 1] + task_dp[i - 2], low[i - 1] + task_dp[i - 1]); return task_dp[n]; } // Driver program to test above function static void Main() { int n = 5; int []high = {3, 6, 8, 7, 6}; int []low = {1, 5, 4, 5, 3}; Console.WriteLine(maxTasks(high, low, n)); } } // This code is contributed by mits |
Javascript
<script> // A DP based javascript program to find maximum tasks. // Returns the maximum among the 2 numbers function max(x , y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n function maxTasks(high , low , n) { // An array task_dp that stores the maximum // task done var task_dp = Array.from({length: n+1}, (_, i) => 0); // If n = 0, no solution exists task_dp[0] = 0; // If n = 1, high effort task on that day will // be the solution task_dp[1] = high[0]; // Fill the entire array determining which // task to choose on day i for (i = 2; i <= n; i++) task_dp[i] = Math.max(high[i - 1] + task_dp[i - 2], low[i - 1] + task_dp[i - 1]); return task_dp[n]; } // Driver code var n = 5; var high = [3, 6, 8, 7, 6]; var low = [1, 5, 4, 5, 3]; document.write(maxTasks(high, low, n)); // This code is contributed by Amit Katiyar </script> |
PHP
<?php // A DP based PHP program to find maximum tasks. // Returns the maximum among the 2 numbers function max1( $x , $y ) { return ( $x > $y ? $x : $y ); } // Returns maximum amount of task that can be // done till day n function maxTasks( $high , $low , $n ) { // An array task_dp that stores the maximum // task done $task_dp = array ( $n + 1); // If n = 0, no solution exists $task_dp [0] = 0; // If n = 1, high effort task on that day will // be the solution $task_dp [1] = $high [0]; // Fill the entire array determining which // task to choose on day i for ( $i = 2; $i <= $n ; $i ++) $task_dp [ $i ] = max( $high [ $i - 1] + $task_dp [ $i - 2], $low [ $i - 1] + $task_dp [ $i - 1]); return $task_dp [ $n ]; } // Driver code { $n = 5; $high = array (3, 6, 8, 7, 6); $low = array (1, 5, 4, 5, 3); echo (maxTasks( $high , $low , $n )); } // This code is contributed by Code_Mech. |
20
Time Complexity : O(n)
Auxiliary Space: O(n)
Efficient approach: Space optimization
To optimize the space complexity of the above approach, we can eliminate the need for an array task_dp and instead use variables to store the previous maximum values. This will reduce the space complexity from O(n) to O(1).
Implementation Steps:
- Define a function maxTasks that takes in two arrays high and low, and the integer n representing the number of days.
- Initialize two variables: prev_prev to store the previous-to-previous maximum value, and prev to store the previous maximum value. Set prev to the first element of the high array.
- Iterate from i = 2 to n (inclusive) to calculate the maximum amount of tasks that can be done till day n.
- Inside the loop, calculate the current maximum value curr using the formula max(high[i – 1] + prev_prev, low[i – 1] + prev).
- Update prev_prev with the value of prev, and prev with the value of curr for the next iteration.
- After the loop, prev will hold the maximum amount of tasks that can be done till day n.
- Return the value of prev.
Implementation:
C++
#include <iostream> using namespace std; // Returns the maximum among the 2 numbers int max( int x, int y) { return (x > y ? x : y); } // Returns maximum amount of task that can be // done till day n int maxTasks( int high[], int low[], int n) { int prev_prev = 0; // Variable to store the previous to previous maximum value int prev = high[0]; // Variable to store the previous maximum value for ( int i = 2; i <= n; i++) { int curr = max(high[i - 1] + prev_prev, low[i - 1] + prev); // Calculate the current maximum value prev_prev = prev; // Update the previous to previous maximum value for the next iteration prev = curr; // Update the previous maximum value for the next iteration } return prev; // Return the maximum value } int main() { int n = 5; int high[] = {3, 6, 8, 7, 6}; int low[] = {1, 5, 4, 5, 3}; cout << maxTasks(high, low, n); return 0; } |
Java
import java.util.*; public class GFG { // Returns the maximum among the 2 numbers public static int max( int x, int y) { return (x > y ? x : y); } // Returns the maximum amount of tasks that can be done till day n public static int maxTasks( int [] high, int [] low, int n) { int prev_prev = 0 ; // Variable to store the previous-to-previous maximum value int prev = high[ 0 ]; // Variable to store the previous maximum value for ( int i = 2 ; i <= n; i++) { int curr = max(high[i - 1 ] + prev_prev, low[i - 1 ] + prev); // Calculate the current maximum value prev_prev = prev; // Update the previous-to-previous maximum value for the next iteration prev = curr; // Update the previous maximum value for the next iteration } return prev; // Return the maximum value } public static void main(String[] args) { int n = 5 ; int [] high = { 3 , 6 , 8 , 7 , 6 }; int [] low = { 1 , 5 , 4 , 5 , 3 }; System.out.println(maxTasks(high, low, n)); } } |
Python3
def max_val(x, y): # Return the maximum of two values return x if x > y else y def max_tasks(high, low, n): # Initialize variables to keep track of previous two task values prev_prev = 0 prev = high[ 0 ] # Loop through the tasks starting from the third task (index 2) for i in range ( 2 , n + 1 ): # Calculate the maximum value considering two choices: # 1. Doing the current task from the "high" list and skipping the previous task # 2. Doing the current task from the "low" list and doing the previous task curr = max_val(high[i - 1 ] + prev_prev, low[i - 1 ] + prev) # Update the previous two task values for the next iteration prev_prev = prev prev = curr # Return the maximum value achievable by completing tasks return prev def main(): n = 5 high = [ 3 , 6 , 8 , 7 , 6 ] # High value for each task low = [ 1 , 5 , 4 , 5 , 3 ] # Low value for each task print (max_tasks(high, low, n)) # Print the maximum achievable value if __name__ = = "__main__" : main() |
C#
using System; class Program { // Returns the maximum among the two numbers static int Max( int x, int y) { return (x > y ? x : y); } // Returns the maximum amount of task that can be done till day n static int MaxTasks( int [] high, int [] low, int n) { int prevPrev = 0; // Variable to store the previous to previous maximum value int prev = high[0]; // Variable to store the previous maximum value for ( int i = 2; i <= n; i++) { int current = Max(high[i - 1] + prevPrev, low[i - 1] + prev); // Calculate the current maximum value prevPrev = prev; // Update the previous to previous maximum value for the next iteration prev = current; // Update the previous maximum value for the next iteration } return prev; // Return the maximum value } static void Main() { int n = 5; int [] high = { 3, 6, 8, 7, 6 }; int [] low = { 1, 5, 4, 5, 3 }; // Print the result of maxTasks function Console.WriteLine(MaxTasks(high, low, n)); } } |
Javascript
// Returns the maximum among the 2 numbers function max(x, y) { return x > y ? x : y; } // Returns the maximum amount of tasks that can be done till day n function maxTasks(high, low, n) { let prevPrev = 0; // Variable to store the previous-to-previous maximum value let prev = high[0]; // Variable to store the previous maximum value for (let i = 2; i <= n; i++) { let curr = max(high[i - 1] + prevPrev, low[i - 1] + prev); // Calculate the current maximum value prevPrev = prev; // Update the previous-to-previous maximum value for the next iteration prev = curr; // Update the previous maximum value for the next iteration } return prev; // Return the maximum value } // Driver code let n = 5; let high = [3, 6, 8, 7, 6]; let low = [1, 5, 4, 5, 3]; console.log(maxTasks(high, low, n)); |
Output
20
Time Complexity : O(n)
Auxiliary Space: O(1)
Contact Us