Se le dan n días y para cada día (di) puede realizar tareas de alto esfuerzo (hi) o tareas de bajo esfuerzo (li) o ninguna tarea con la restricción de que puede elegir tareas de alto esfuerzo solo si elige ninguna tarea el día anterior. Escribe un programa para encontrar la cantidad máxima de tareas que puedes realizar dentro de estos n días.
Ejemplos:
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
Subestructura óptima
Para encontrar la cantidad máxima de tareas realizadas hasta el i-ésimo día, necesitamos comparar 2 opciones:
- Elija tareas de alto esfuerzo en ese día, luego encuentre la cantidad máxima de tareas realizadas hasta el (i – 2) día.
- Vaya a la tarea de bajo esfuerzo en ese día y encuentre la cantidad máxima de tareas realizadas hasta el (i – 1) día.
Sea high [1…n] la array de entrada para la cantidad de tareas de alto esfuerzo en el i-ésimo día y low [1…n] sea la array de entrada para la cantidad de tareas de bajo esfuerzo en el i-ésimo día.
Sea max_task (high [], low [], i) la función que devuelve la cantidad máxima de tareas realizadas hasta el iésimo día, por lo que devolverá max(high[i] + max_task(high, low, (i – 2)) , bajo [i] + max_task (alto, bajo, (i – 1)))
Por lo tanto, el problema tiene una propiedad de subestructura óptima ya que el problema se puede resolver usando soluciones a los subproblemas.
Subproblemas superpuestos
A continuación se presenta una implementación recursiva simple del problema de tarea de alto esfuerzo frente a bajo esfuerzo. La implementación simplemente sigue la estructura recursiva mencionada anteriormente. Entonces, el problema de tarea de alto esfuerzo vs. bajo esfuerzo tiene las dos propiedades de un problema de programación dinámica.
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("%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
?>
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>
Producción :
20
Cabe señalar que la función anterior calcula los mismos subproblemas una y otra vez.
Por lo tanto, este problema tiene la propiedad de subproblemas superpuestos. Por lo tanto, el problema de tarea de alto esfuerzo frente a bajo esfuerzo tiene las dos propiedades de un problema de programación dinámica.
Solución de programación dinámica
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.
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
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.
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>
Producción:
20
Complejidad de tiempo: O(n) Akash Aggarwal
contribuye con este artículo . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA