给你n天的时间，每天（di）你可以执行高强度任务（hi）或低强度任务（li）或无任务，限制条件是，只有在前一天没有选择任务时，你才能选择高强度任务。编写一个程序，找出在这n天内可以执行的最大任务量。 例如：
null
No. of days (n) = 5Day L.E. H.E1 1 32 5 63 4 84 5 75 3 6Maximum amount of tasks = 3 + 5 + 4 + 5 + 3 = 20
最优子结构 为了找出第i天完成的最大任务量，我们需要比较两种选择：
- 在那一天进行高强度的任务，然后找出在第（i–2）天之前完成的最大任务量。
- 在那一天进行低强度的任务，找出在第（i–1）天之前完成的最大任务量。
设高[1…n]为第i天高工作量任务量的输入数组，低[1…n]为第i天低工作量任务量的输入数组。 设max_task（high[]，low[]，i）是返回第i天完成的最大任务量的函数，因此它将返回max（high[i]+max_task（high，low，（i–2）），low[i]+max_task（high，low，（i–1））） 因此，该问题具有最优子结构性质，因为可以使用子问题的解来解决该问题。 重叠子问题 下面是高强度任务与低强度任务问题的简单递归实现。实现简单地遵循上面提到的递归结构。所以，高强度任务和低强度任务问题都具有动态规划问题的性质。
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> |
输出：
20
应该注意的是，上面的函数一次又一次地计算相同的子问题。 因此，该问题具有重叠子问题的性质。因此，高强度任务和低强度任务问题都具有动态规划问题的性质。 动态规划解法
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> |
输出：
20
时间复杂性： O（n） 本文由 阿卡什·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
