Dados tres enteros n , h y p , donde n es el número de temas, h es el tiempo restante (en horas) y p son las calificaciones para aprobar. También se dan dos arrays marcas[] y tiempo[] donde marcas[i] son las marcas para el i -ésimo tema y tiempo[i] es el tiempo necesario para aprender el i -ésimo tema. La tarea consiste en encontrar la máxima puntuación que se puede obtener estudiando el máximo número de temas.
Ejemplos:
Entrada: n = 4, h = 10, p = 10, marcas[] = {6, 4, 2, 8}, tiempo[] = {4, 6, 2, 7}
Salida: 10
Cualquiera de los temas con marcas marcas Se pueden preparar [2] y puntos [3]
o se pueden preparar puntos [0] y puntos [1]
Ambos casos darán lugar a 10 puntos en total
, que son iguales a los puntos de aprobación.
Entrada: n = 5, h = 40, p = 21, marcas[] = {10, 10, 10, 10, 3}, tiempo[] = {12, 16, 20, 24, 8}
Salida: 36
Enfoque: El problema dado es una versión modificada de 0/1 Mochila en la que debemos considerar tomar una bolsa o ignorarla.
Lo que cambia en esta pregunta son las condiciones de restricción que nos dan el tiempo que toma un tema en particular y el tiempo máximo que queda para los exámenes.
Implementación:
Procediendo de la misma manera que el problema de la mochila 0/1, consideraremos leer un tema si se puede leer en el tiempo sobrante dado para el examen; de lo contrario, ignore ese tema y pase al siguiente tema. De esta manera calcularemos la suma máxima de puntos de ponderación que un estudiante puede obtener en el marco de tiempo dado.
- Condiciones base: cuando el tiempo es 0 o el número de temas es 0 , las calificaciones calculadas también serán 0 .
- Si el tiempo sobrante es menor que el tiempo necesario para cubrir el i -ésimo tema, ignórelo y siga adelante.
- Ahora surgen dos casos (Tenemos que encontrar el máximo de los dos)
- Considere leer ese tema.
- Ignora ese tema.
- Ahora, para encontrar las calificaciones máximas que se pueden lograr, tenemos que retroceder en nuestro camino de temas considerados para la lectura. Haremos un bucle desde la parte inferior izquierda de la array para comenzar y seguir agregando el peso del tema si lo hemos considerado en la array.
- Ahora T[no_of_topics-1][total_time-1] contendrá las calificaciones finales.
- Si las calificaciones finales son menores que las calificaciones de aprobación, imprima -1 ; de lo contrario, imprima las calificaciones calculadas.
A continuación se muestra la implementación del enfoque anterior:
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 duration
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[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 no 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 code
int 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 approach
import java.io.*;
class GFG
{
// 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)
{
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 no 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 no 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 approach
using System;
class GFG
{
// 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)
{
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 no 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 no 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>
Producción:
10
Complejidad del tiempo : O (n*t) (donde n es el número de temas y t es el tiempo total empleado)
Complejidad espacial : O (n*t)