Dynamic Programming | High-effort vs. Low-effort Tasks Problem - GeeksforGeeks

Dynamic Programming | High-effort vs. Low-effort Tasks Problem - GeeksforGeeks
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.

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

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)));

}

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];

}

Read full article from Dynamic Programming | High-effort vs. Low-effort Tasks Problem - GeeksforGeeks