dynamic-programming - 动态规划的递归关系以获得最大学分

Question

我的问题是我有固定的时间，我必须获得最高的利润。
如何为动态程序编写递归关系？

我的问题的一个例子：
时间是[3, 2, 4, 2, 1]
利润是[20, 15, 20, 25, 20]
要求的时间是6

答案应该是选择有利润65的指数的时间。0,3,420 + 25 + 20 = 65

标签： dynamic-programming

Answer 1

让我们定义一个函数，该函数f(i,h)从具有索引（0,1,2...,i）的利润中精确地给出 h 小时的最大利润，那么您的案例的结果是f(size_of_the_array , number_of_hours) = f(5,6)。

主要的递归公式将如下所示：

f(i,h) = max(w1,w2);
w1 = f(i-1,h); //don't consider the i-th profit in the sum
w2 = f(i-1,h-time[i]) + profit[i]; : h>=time[i] //consider the i-th profit in the sum

这类似于动态规划中称为0-1Knapsack的标准问题

你可以先研究它，然后你的问题就会很容易解决。