Given three integer n, h and p where n is the number of topics, h is the time left (in hours) and p is the passing marks. Also given two arrays marks[] and time[] where marks[i] is the marks for the ith topic and time[i] is the time required to learn the ith topic. The task is to find the maximum marks that can be obtained by studying maximum number of topics.
Examples:
Input: n = 4, h = 10, p = 10, marks[] = {6, 4, 2, 8}, time[] = {4, 6, 2, 7}
Output: 10
Either the topics with marks marks[2] and marks[3]
can be prepared or marks[0] and marks[1] can be prepared
Both cases will lead to 10 marks in total
which are equal to the passing marks.
Input: n = 5, h = 40, p = 21, marks[] = {10, 10, 10, 10, 3}, time[] = {12, 16, 20, 24, 8}
Output: 36
Approach: The given problem is a modified version of 0/1 Knapsack where we have to either consider taking a bag or else ignore that bag.
What changes in this question is the constraint conditions that we are given the time a particular topic takes and maximum time left for the exams.
Implementation:
Proceeding in the same way as 0/1 Knapsack problem we will be consider reading a topic if it can be read in the given leftover time for the exam otherwise ignore that topic and move to next topic. This way we will calculate the maximum weightage marks sum that a student can score in the given time frame.
- Base conditions: When time is 0 or number of topics is 0 then the calculated marks will also be 0.
- If the leftover time is less than the time needed to cover the ith topic then ignore that topic and move forward.
- Now two cases arise (We have to find the maximum of the two)
- Consider reading that topic.
- Ignore that topic.
- Now to find the maximum marks that can be achieved we have to backtrack our path of topics considered for reading. We will loop from bottom left of matrix to start and keep adding topic weight if we have considered it in the matrix.
- Now T[no_of_topics-1][total_time-1] will contain the final marks.
- If the final marks are less than the passing marks then print -1 else print the calculated marks.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum marks// by considering topics which can be// completed in the given time durationint MaximumMarks(int marksarr[], int timearr[], int h, int n, int p){ int no_of_topics = n + 1; int total_time = h + 1; int T[no_of_topics][total_time]; // Initialization // If we are given 0 time // then nothing can be done // So all values are 0 for (int i = 0; i < no_of_topics; i++) { T[i][0] = 0; } // If we are given 0 topics // then the time required // will be 0 for sure for (int j = 0; j < total_time; j++) { T[0][j] = 0; } // Calculating the maximum marks // that can be achieved under // the given time constraints for (int i = 1; i < no_of_topics; i++) { for (int j = 1; j < total_time; j++) { // If time taken to read that topic // is more than the time left now at // position j then do not read that topic if (j < timearr[i]) { T[i][j] = T[i - 1][j]; } else { /*Two cases arise: 1) Considering current topic 2) Ignoring current topic We are finding maximum of (current topic weightage + topics which can be done in leftover time - current topic time) and ignoring current topic weightage sum */ T[i][j] = max(marksarr[i] + T[i - 1][j - timearr[i]], T[i - 1][j]); } } } // Moving upwards in table from bottom right // to calculate the total time taken to // read the topics which can be done in // given time and have highest weightage sum int i = no_of_topics - 1, j = total_time - 1; int sum = 0; while (i > 0 && j > 0) { // It means we have not considered // reading this topic for // max weightage sum if (T[i][j] == T[i - 1][j]) { i--; } else { // Adding the topic time sum += timearr[i]; // Evaluating the left over time after // considering this current topic j -= timearr[i]; // One topic completed i--; } } // It contains the maximum weightage sum // formed by considering the topics int marks = T[no_of_topics - 1][total_time - 1]; // Condition when exam cannot be passed if (marks < p) return -1; // Return the marks that // can be obtained after // passing the exam return sum;}// Driver codeint main(){ // Number of topics, hours left // and the passing marks int n = 4, h = 10, p = 10; // n+1 is taken for simplicity in loops // Array will be indexed starting from 1 int marksarr[n + 1] = { 0, 6, 4, 2, 8 }; int timearr[n + 1] = { 0, 4, 6, 2, 7 }; cout << MaximumMarks(marksarr, timearr, h, n, p); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG{ // Function to return the maximum marks// by considering topics which can be// completed in the given time durationstatic int MaximumMarks(int marksarr[], int timearr[], int h, int n, int p){ int no_of_topics = n + 1; int total_time = h + 1; int T[][] = new int[no_of_topics][total_time]; // Initialization // If we are given 0 time // then nothing can be done // So all values are 0 for (int i = 0; i < no_of_topics; i++) { T[i][0] = 0; } // If we are given 0 topics // then the time required // will be 0 for sure for (int j = 0; j < total_time; j++) { T[0][j] = 0; } // Calculating the maximum marks // that can be achieved under // the given time constraints for (int i = 1; i < no_of_topics; i++) { for (int j = 1; j < total_time; j++) { // If time taken to read that topic // is more than the time left now at // position j then do not read that topic if (j < timearr[i]) { T[i][j] = T[i - 1][j]; } else { /*Two cases arise: 1) Considering current topic 2) Ignoring current topic We are finding maximum of (current topic weightage + topics which can be done in leftover time - current topic time) and ignoring current topic weightage sum */ T[i][j] = Math.max(marksarr[i] + T[i - 1][j - timearr[i]], T[i - 1][j]); } } } // Moving upwards in table from bottom right // to calculate the total time taken to // read the topics which can be done in // given time and have highest weightage sum int i = no_of_topics - 1, j = total_time - 1; int sum = 0; while (i > 0 && j > 0) { // It means we have not considered // reading this topic for // max weightage sum if (T[i][j] == T[i - 1][j]) { i--; } else { // Adding the topic time sum += timearr[i]; // Evaluating the left over time after // considering this current topic j -= timearr[i]; // One topic completed i--; } } // It contains the maximum weightage sum // formed by considering the topics int marks = T[no_of_topics - 1][total_time - 1]; // Condition when exam cannot be passed if (marks < p) return -1; // Return the marks that // can be obtained after // passing the exam return sum;} // Driver code public static void main (String[] args) { // Number of topics, hours left // and the passing marks int n = 4, h = 10, p = 10; // n+1 is taken for simplicity in loops // Array will be indexed starting from 1 int marksarr[] = { 0, 6, 4, 2, 8 }; int timearr[] = { 0, 4, 6, 2, 7 }; System.out.println( MaximumMarks(marksarr, timearr, h, n, p)); }}// This code is contributed by vt_m |
Python3
# Python3 implementation of the approach import numpy as np# Function to return the maximum marks # by considering topics which can be # completed in the given time duration def MaximumMarks(marksarr, timearr, h, n, p) : no_of_topics = n + 1; total_time = h + 1; T = np.zeros((no_of_topics, total_time)); # Initialization # If we are given 0 time # then nothing can be done # So all values are 0 for i in range(no_of_topics) : T[i][0] = 0; # If we are given 0 topics # then the time required # will be 0 for sure for j in range(total_time) : T[0][j] = 0; # Calculating the maximum marks # that can be achieved under # the given time constraints for i in range(1, no_of_topics) : for j in range(1, total_time) : # If time taken to read that topic # is more than the time left now at # position j then do not read that topic if (j < timearr[i]) : T[i][j] = T[i - 1][j]; else : """Two cases arise: 1) Considering current topic 2) Ignoring current topic We are finding maximum of (current topic weightage + topics which can be done in leftover time - current topic time) and ignoring current topic weightage sum """ T[i][j] = max(marksarr[i] + T[i - 1][j - timearr[i]], T[i - 1][j]); # Moving upwards in table from bottom right # to calculate the total time taken to # read the topics which can be done in # given time and have highest weightage sum i = no_of_topics - 1; j = total_time - 1; sum = 0; while (i > 0 and j > 0) : # It means we have not considered # reading this topic for # max weightage sum if (T[i][j] == T[i - 1][j]) : i -= 1; else : # Adding the topic time sum += timearr[i]; # Evaluating the left over time after # considering this current topic j -= timearr[i]; # One topic completed i -= 1; # It contains the maximum weightage sum # formed by considering the topics marks = T[no_of_topics - 1][total_time - 1]; # Condition when exam cannot be passed if (marks < p) : return -1; # Return the marks that # can be obtained after # passing the exam return sum; # Driver code if __name__ == "__main__" : # Number of topics, hours left # and the passing marks n = 4; h = 10; p = 10; # n+1 is taken for simplicity in loops # Array will be indexed starting from 1 marksarr = [ 0, 6, 4, 2, 8 ]; timearr = [ 0, 4, 6, 2, 7 ]; print(MaximumMarks(marksarr, timearr, h, n, p)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{ // Function to return the maximum marks// by considering topics which can be// completed in the given time durationstatic int MaximumMarks(int []marksarr, int []timearr, int h, int n, int p){ int no_of_topics = n + 1; int total_time = h + 1; int [,]T = new int[no_of_topics,total_time]; int i,j; // Initialization // If we are given 0 time // then nothing can be done // So all values are 0 for (i = 0; i < no_of_topics; i++) { T[i, 0] = 0; } // If we are given 0 topics // then the time required // will be 0 for sure for (j = 0; j < total_time; j++) { T[0, j] = 0; } // Calculating the maximum marks // that can be achieved under // the given time constraints for (i = 1; i < no_of_topics; i++) { for (j = 1; j < total_time; j++) { // If time taken to read that topic // is more than the time left now at // position j then do not read that topic if (j < timearr[i]) { T[i, j] = T[i - 1, j]; } else { /*Two cases arise: 1) Considering current topic 2) Ignoring current topic We are finding maximum of (current topic weightage + topics which can be done in leftover time - current topic time) and ignoring current topic weightage sum */ T[i, j] = Math.Max(marksarr[i] + T[i - 1, j - timearr[i]], T[i - 1, j]); } } } // Moving upwards in table from bottom right // to calculate the total time taken to // read the topics which can be done in // given time and have highest weightage sum i = no_of_topics - 1; j = total_time - 1; int sum = 0; while (i > 0 && j > 0) { // It means we have not considered // reading this topic for // max weightage sum if (T[i, j] == T[i - 1, j]) { i--; } else { // Adding the topic time sum += timearr[i]; // Evaluating the left over time after // considering this current topic j -= timearr[i]; // One topic completed i--; } } // It contains the maximum weightage sum // formed by considering the topics int marks = T[no_of_topics - 1, total_time - 1]; // Condition when exam cannot be passed if (marks < p) return -1; // Return the marks that // can be obtained after // passing the exam return sum;} // Driver code public static void Main (String[] args) { // Number of topics, hours left // and the passing marks int n = 4, h = 10, p = 10; // n+1 is taken for simplicity in loops // Array will be indexed starting from 1 int []marksarr = { 0, 6, 4, 2, 8 }; int []timearr = { 0, 4, 6, 2, 7 }; Console.WriteLine( MaximumMarks(marksarr, timearr, h, n, p)); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximum marks // by considering topics which can be // completed in the given time duration function MaximumMarks(marksarr, timearr, h, n, p) { let no_of_topics = n + 1; let total_time = h + 1; let T = new Array(no_of_topics); for (let i = 0; i < no_of_topics; i++) { T[i] = new Array(total_time); for (let j = 0; j < total_time; j++) { T[i][j] = 0; } } // Initialization // If we are given 0 time // then nothing can be done // So all values are 0 for (let i = 0; i < no_of_topics; i++) { T[i][0] = 0; } // If we are given 0 topics // then the time required // will be 0 for sure for (let j = 0; j < total_time; j++) { T[0][j] = 0; } // Calculating the maximum marks // that can be achieved under // the given time constraints for (let i = 1; i < no_of_topics; i++) { for (let j = 1; j < total_time; j++) { // If time taken to read that topic // is more than the time left now at // position j then do not read that topic if (j < timearr[i]) { T[i][j] = T[i - 1][j]; } else { /*Two cases arise: 1) Considering current topic 2) Ignoring current topic We are finding maximum of (current topic weightage + topics which can be done in leftover time - current topic time) and ignoring current topic weightage sum */ T[i][j] = Math.max(marksarr[i] + T[i - 1][j - timearr[i]], T[i - 1][j]); } } } // Moving upwards in table from bottom right // to calculate the total time taken to // read the topics which can be done in // given time and have highest weightage sum let i = no_of_topics - 1, j = total_time - 1; let sum = 0; while (i > 0 && j > 0) { // It means we have not considered // reading this topic for // max weightage sum if (T[i][j] == T[i - 1][j]) { i--; } else { // Adding the topic time sum += timearr[i]; // Evaluating the left over time after // considering this current topic j -= timearr[i]; // One topic completed i--; } } // It contains the maximum weightage sum // formed by considering the topics let marks = T[no_of_topics - 1][total_time - 1]; // Condition when exam cannot be passed if (marks < p) return -1; // Return the marks that // can be obtained after // passing the exam return sum; } // Number of topics, hours left // and the passing marks let n = 4, h = 10, p = 10; // n+1 is taken for simplicity in loops // Array will be indexed starting from 1 let marksarr = [ 0, 6, 4, 2, 8 ]; let timearr = [ 0, 4, 6, 2, 7 ]; document.write( MaximumMarks(marksarr, timearr, h, n, p));</script> |
Output
10
Time Complexity : O (n*t) ( where n is number of topics and t is total time taken)
Space Complexity : O (n*t)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size h+1.
- Set a base case by initializing the values of DP .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Initialize a variable sum to store the final answer and update it by iterating through the Dp.
- At last return and print the final answer stored in sum.
Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum marks// by considering topics which can be// completed in the given time durationint MaximumMarks(int marksarr[], int timearr[], int h, int n, int p){ // Initialize dp to store // computations of subproblems vector<int> T(h + 1, 0); // iterate over subproblems and get the current // solution for previous computations for (int i = 1; i <= n; i++) { for (int j = h; j >= timearr[i]; j--) { T[j] = max(T[j], marksarr[i] + T[j - timearr[i]]); } } int sum = 0; // update sum for (int j = h; j >= 0; j--) { if (T[j] >= p) { sum = j; break; } } // return final answer return (sum > 0 ? sum : -1);}// Driver codeint main(){ int n = 4, h = 10, p = 10; int marksarr[n + 1] = { 0, 6, 4, 2, 8 }; int timearr[n + 1] = { 0, 4, 6, 2, 7 }; // function call cout << MaximumMarks(marksarr, timearr, h, n, p); return 0;} |
Java
import java.util.*;public class Main { // Function to return the maximum marks // by considering topics which can be // completed in the given time duration static int MaximumMarks(int marksarr[], int timearr[], int h, int n, int p) { // Initialize dp to store // computations of subproblems ArrayList<Integer> T = new ArrayList<>(Collections.nCopies(h + 1, 0)); // iterate over subproblems and get the current // solution for previous computations for (int i = 1; i <= n; i++) { for (int j = h; j >= timearr[i]; j--) { T.set(j, Math.max(T.get(j), marksarr[i] + T.get(j - timearr[i]))); } } int sum = 0; // update sum for (int j = h; j >= 0; j--) { if (T.get(j) >= p) { sum = j; break; } } // return final answer return (sum > 0 ? sum : -1); } // Driver code public static void main(String[] args) { int n = 4, h = 10, p = 10; int marksarr[] = { 0, 6, 4, 2, 8 }; int timearr[] = { 0, 4, 6, 2, 7 }; // function call System.out.println(MaximumMarks(marksarr, timearr, h, n, p)); }} |
Python
# Python implementation of the approach# Function to return the maximum marks# by considering topics which can be# completed in the given time durationdef MaximumMarks(marksarr, timearr, h, n, p): # Initialize dp to store # computations of subproblems T = [0] * (h+1) # iterate over subproblems and get the current # solution for previous computations for i in range(1, n+1): for j in range(h, timearr[i]-1, -1): T[j] = max(T[j], marksarr[i] + T[j-timearr[i]]) sum = 0 # update sum for j in range(h, -1, -1): if T[j] >= p: sum = j break # return final answer return sum if sum > 0 else -1# Driver codeif __name__ == "__main__": n, h, p = 4, 10, 10 marksarr = [0, 6, 4, 2, 8] timearr = [0, 4, 6, 2, 7] # function call print(MaximumMarks(marksarr, timearr, h, n, p)) |
C#
using System;using System.Collections.Generic;public class MainClass{ // Function to return the maximum marks // by considering topics which can be // completed in the given time duration static int MaximumMarks(int[] marksarr, int[] timearr, int h, int n, int p) { // Initialize T to store // computations of subproblems List<int> T = new List<int>(new int[h + 1]); // iterate over subproblems and get the current // solution for previous computations for (int i = 1; i <= n; i++) { for (int j = h; j >= timearr[i]; j--) { T[j] = Math.Max(T[j], marksarr[i] + T[j - timearr[i]]); } } int sum = 0; // update sum for (int j = h; j >= 0; j--) { if (T[j] >= p) { sum = j; break; } } // return final answer return (sum > 0 ? sum : -1); } // Driver code public static void Main(string[] args) { int n = 4, h = 10, p = 10; int[] marksarr = { 0, 6, 4, 2, 8 }; int[] timearr = { 0, 4, 6, 2, 7 }; // function call Console.WriteLine(MaximumMarks(marksarr, timearr, h, n, p)); }} |
Javascript
// Function to return the maximum marks// by considering topics which can be// completed in the given time durationfunction MaximumMarks(marksarr, timearr, h, n, p) { // Initialize an array T to store subproblem solutions const T = new Array(h + 1).fill(0); // Iterate over topics for (let i = 1; i <= n; i++) { // Iterate over time durations for (let j = h; j >= timearr[i]; j--) { // Calculate the maximum marks that can be obtained // by considering the current topic and time duration T[j] = Math.max(T[j], marksarr[i] + T[j - timearr[i]]); } } // Initialize a sum variable let sum = 0; // Find the maximum time duration within which at least p marks can be obtained for (let j = h; j >= 0; j--) { if (T[j] >= p) { sum = j; break; } } // Return the final answer return sum > 0 ? sum : -1;}// Driver Codeconst n = 4; const h = 10; const p = 10; const marksarr = [0, 6, 4, 2, 8];const timearr = [0, 4, 6, 2, 7]; // Function callconsole.log(MaximumMarks(marksarr, timearr, h, n, p)); // Print the result |
Output:
10
Time Complexity: O (n*h) ( where n is number of topics and t is time left in hour)
Auxiliary Space : O (h)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
