用动态规划方法设计求解该问题的最有效算法

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背包问题，可以使用动态规划轻松解决。