Question

A student has too much work to complete before the deadline is due. Each assignment counts as a different part of the overall grade and each requires a different amount of time to complete.

How can we optimize the final grade (the student earns all of the points possible for each assignment) with a dynamic programming solution?

What would the runtime be of this solution and any complicating factors?

Answer 1

/*
Made By : Arun Kumar
Time Complexity : O(maxtime x numberofassignments)
Assumption : User is allowed to even fail in a subject i.e. not even studying a course for a bit.
*/
#include<bits/stdc++.h>

using namespace std;
int main(){
int maxtime,numofassigns;
vector < pair< int,int > > assigns;

cout<<"Enter Maximum time Left : "<<endl;
cin>>maxtime;
cout<<"Enter number of assigns : "<<endl;
cin>>numofassigns;
cout<<"Enter time and credits for each course : "<<endl;
for(int i=0;i<numofassigns;++i) {   
int a,b;
cin>>a>>b;
assigns.push_back(make_pair(a,b)); //vector to store time for a particular course and its credits
}

vector <int> ansdp(maxtime + 1,0);
for(auto x:assigns){ //for all courses
for(int i = maxtime - x.first;i>=0;--i){ //for all i in range(maxtime - x.first,0) since maximum time is maxtime
if(i == 0 or ansdp[i] != 0)
ansdp[i+x.first] = max(ansdp[i+x.first],ansdp[i]+x.second); //maximum credits in a particular time
}
}
int maxcredits = 0;
for(int i = maxtime;i>=0;--i){
maxcredits = max(maxcredits,ansdp[i]); //maximum credits you can acquire
}   
cout<<endl<<"Maximum credits you can acquire in time "<<maxtime<<" are : "<<maxcredits<<endl;
return 0;
}