Tutorialspoint.dev

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 a high-effort tasks only if you chose 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       6
Maximum amount of tasks 
        = 3 + 5 + 4 + 5 + 3 
        = 20




Optimal Substructure
To find the maximum amount of tasks done till i’th day, we need to compare 2 choices:

  1. Go for high effort tasks on that day, then find the maximum amount of tasks done till (i – 2) th day.
  2. 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.

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("%dn", maxTasks(high, low, n));
    return 0;
}

Java

// A naive recursive Java program 
// to find maximum tasks.
  
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.

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
?>


Output :

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.

Dynamic Programming Solution

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("%dn", maxTasks(high, low, n));
    return 0;
}

Java

// A DP based Java program to find maximum tasks.
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.

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

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.


Output:

20

Time Complexity : O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter