Problem 60: Job Scheduling with Deadlines (Bitmask DP)
Problem Statement: Given n jobs each with a deadline and profit, schedule them such that no two jobs overlap and maximize total profit. Use bitmask dynamic programming to solve for n up to 20.
Input
The first line contains an integer n. Each of the next n lines contains two integers: deadline and profit.
Output
Print the maximum profit achievable by scheduling a subset of jobs.
Examples
Input:
4
4 70
2 60
4 50
3 40
Output:
120
Solution Explanation
With n up to 20, bitmask DP is feasible. Each state represents a subset of jobs taken. Validate feasibility (jobs must complete before their deadlines) and maximize profit.
Solution in C++
#include
#include
#include
using namespace std;
struct Job {
int d, p;
};
int main(){
int n;
cin >> n;
vector jobs(n);
for(int i = 0; i < n; i++){
cin >> jobs[i].d >> jobs[i].p;
}
int N = 1 << n;
vector dp(N, 0);
vector timeUsed(N, 0);
for(int mask = 0; mask < N; mask++){
for(int j = 0; j < n; j++){
if(!(mask & (1 << j))){
int next = mask | (1 << j);
if(timeUsed[mask] + 1 <= jobs[j].d){
dp[next] = max(dp[next], dp[mask] + jobs[j].p);
timeUsed[next] = max(timeUsed[next], timeUsed[mask] + 1);
}
}
}
}
int ans = 0;
for(auto x : dp) ans = max(ans, x);
cout << ans << "\n";
return 0;
}