用动态规划方法设计最有效的算法

Question

假设你在考试，你有120分钟的时间，但你不能解决问题，因为你的时间有限。例如，完成问题所需的时间和点如下:

输入图片描述

所以我们需要设计最有效的算法，使用动态规划方法来计算你在可用时间内将采取的最高点。

我的代码如下;

static int maxPoints(int points[], int time[],int n) {

if(n<=0) {
return 0;
}
else {
return Math.max(points[n-1]+maxPoints(points,time,(n-2)),
time[n - 1] + maxPoints(points, time, (n - 1)));
}
}

public static void main(String[] args) {
int n=10;
int points[]= {4,9,5,12,14,6,12,20,7,10};
int time[]= {1,15,2,3,20,120};
System.out.println();

}

但是我找不到正确的算法，你能帮我解决这个问题吗?

Answer 1

在你的问题中，每个问题都有一个权重(它需要的时间量)和一个值(它奖励的点数)。总时间(或权重)是有限制的，你需要最大化点(或值)。

这类似于0-1背包问题，它可以很容易地用动态规划来解决。