使用动态规划方法为问题设计最有效的算法

Question

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

enter image description here

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

下面是我的代码；

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 Knapsack Problem，可以使用动态规划轻松求解。

使用动态规划方法为问题设计最有效的算法

Designing most efficient algorithm for the problem with dynamic programming approach

java

algorithm

dynamic-programming