## Thursday, July 28, 2016

### 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];`
`}`