Dynamic Programming: Optimal Exam Question Selection

Problem Description

Given an exam with multiple questions of varying point values and time requirements, design an efficient algorithm to maximize the total points earned within a fixed time limit.

Problem Constraints

1. There are n questions in the exam
2. For each question i:
   • Worth $p_i$ points
   • Takes $m_i$ minutes to solve
   • Must spend full $m_i$ minutes or leave blank (no partial credit)
3. Total exam duration is M minutes
4. The goal is to maximize total points earned

Example

For an exam with 4 questions, the parameters might be:

With a total time limit M = 30 minutes.

Understanding the Solution

Dynamic Programming Approach

This problem is a variation of the 0/1 knapsack problem, where:

• Items are exam questions
• Values are question points
• Weights are time requirements
• Capacity is the total exam duration

Let’s break down the solution step by step.

1. State Definition

Let dp[i][t] represent the maximum points possible using the first i questions within t minutes.

2. Recurrence Relation

For each question i and time t, we have two choices:

• Skip the question
• Take the question if we have enough time

This gives us the recurrence relation:

3. Base Cases

• $dp[0][t] = 0$ for all t (no questions)
• $dp[i][0] = 0$ for all i (no time)

Example Walkthrough

Let’s solve a small example with M = 30 minutes and these questions:

1. 10 points, 5 minutes
2. 25 points, 15 minutes
3. 15 points, 10 minutes

Step by step solution:

1. Initialize dp table with zeros
2. For question 1:
   • Can be solved in 5+ minutes → 10 points
3. For question 2:
   • Can be solved in 15+ minutes → 25 points
   • Or combine with question 1 if time permits
4. For question 3:
   • Consider all combinations with previous questions
   • Find optimal selection within 30-minute limit

Solution Implementation

def optimal_exam_strategy(n, points, minutes, M):
    dp = [[0] * (M + 1) for _ in range(n + 1)]
    selected = [[False] * (M + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for t in range(M + 1):
            # Don't take question i
            dp[i][t] = dp[i-1][t]
            
            # Take question i if enough time
            if t >= minutes[i-1]:
                include = dp[i-1][t - minutes[i-1]] + points[i-1]
                if include > dp[i][t]:
                    dp[i][t] = include
                    selected[i][t] = True
    
    # Reconstruct solution
    solution = []
    curr_time = M
    for i in range(n, 0, -1):
        if selected[i][curr_time]:
            solution.append(i)
            curr_time -= minutes[i-1]
    
    return dp[n][M], solution[::-1]

Complexity Analysis

Time Complexity

• $O(n \times M)$ where:
  • n is the number of questions
  • M is the total time limit
• We fill a table of size (n+1) × (M+1)

Space Complexity

• $O(n \times M)$ for the dp and selected tables
• Additional $O(n)$ for solution reconstruction

Why is this Solution Efficient?

1. Optimal Substructure

   • The optimal solution contains optimal solutions to subproblems
   • Once we find the maximum points for a subset of questions and time, we never need to recalculate

2. Overlapping Subproblems

   • Many subproblems (different time allocations) are reused
   • We store solutions in the dp array to avoid redundant calculations

3. Practical Considerations

   • The algorithm handles all constraints naturally
   • No partial credit is elegantly handled by the 0/1 choice
   • Solution reconstruction gives the actual questions to solve