Assume that you are in exam and you have 120 minutes but you can't solve the questions because you have a limited time. For example, the points and time to be needed to complete the question is below.

enter image description here

So we need to design the most efficient algorithm using dynamic programming approach for calculating highest point you will take in available time.

Here is my code below;

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();
    
}

But i couldn't find the correct algorithm, can you help me with this problem?

CodePudding user response：

In your question, each question has a weight (the amount of time it needs) and a value (the points it awards). There is a constraint on the total time (or weight) and you need to maximise the points (or value).

This becomes analogous to the 0-1 Knapsack Problem, which can easily be solved using dynamic programming.