Рубрики

Найдите максимум тем для подготовки к сдаче экзамена

Даны три целых числа n , h и p, где n — количество тем, h — оставшееся время (в часах), а p — проходные баллы. Также даны два массива меток [] и время [], где метки [i] — метки для i- й темы, а время [i] — время, необходимое для изучения i- й темы. Задача состоит в том, чтобы найти максимальные оценки, которые можно получить, изучив максимальное количество тем.

Примеры:

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

Подход . Данная проблема представляет собой модифицированную версию рюкзака 0/1, в которой мы должны либо рассмотреть возможность взять сумку, либо игнорировать эту сумку.
Изменения в этом вопросе — это условия ограничения, которые нам дают время, затрачиваемое на конкретную тему, и максимальное время, оставшееся до экзаменов.

Реализация:
Действуя так же, как и в задаче о ранце 0/1, мы рассмотрим чтение темы, если она может быть прочитана за заданное оставшееся время для экзамена, в противном случае проигнорируйте эту тему и перейдите к следующей теме. Таким образом, мы рассчитаем максимальную сумму баллов, которую студент может набрать в данный период времени.

  • Базовые условия: если время равно 0 или количество тем равно 0, рассчитанные оценки также будут равны 0 .
  • Если оставшееся время меньше времени, необходимого для рассмотрения i- й темы, игнорируйте эту тему и двигайтесь вперед.
  • Теперь возникают два случая (мы должны найти максимум из двух)
    1. Вы можете прочитать эту тему.
    2. Игнорировать эту тему.
  • Теперь, чтобы найти максимальные оценки, которые могут быть достигнуты, мы должны вернуться к нашему пути тем, рассматриваемых для чтения. Мы начнем цикл с левого нижнего угла матрицы и продолжим добавлять вес темы, если мы учли это в матрице.
  • Теперь T [no_of_topics-1] [total_time-1] будет содержать итоговые оценки.
  • Если конечные метки меньше проходных баллов, выведите -1, иначе выведите рассчитанные метки.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата максимальных оценок
// рассматривая темы, которые могут быть
// завершено в заданный промежуток времени

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];

  

    // Инициализация

  

    // Если нам дано 0 раз

    // тогда ничего не поделаешь

    // Значит, все значения равны 0

    for (int i = 0; i < no_of_topics; i++) {

        T[i][0] = 0;

    }

  

    // Если нам дано 0 тем

    // тогда требуемое время

    // наверняка будет 0

    for (int j = 0; j < total_time; j++) {

        T[0][j] = 0;

    }

  

    // Расчет максимальных оценок

    // это может быть достигнуто в

    // заданные временные ограничения

    for (int i = 1; i < no_of_topics; i++) {

  

        for (int j = 1; j < total_time; j++) {

  

            // Если время потрачено на чтение этой темы

            // больше времени, оставшегося сейчас на

            // позиция j, тогда не читайте эту тему

            if (j < timearr[i]) {

  

                T[i][j] = T[i - 1][j];

            }

            else {

  

                / * Возникают два случая:

                1) Учитывая текущую тему

                2) Игнорирование текущей темы

                Мы находим максимум (текущая тема вес

                + темы, которые можно сделать в оставшееся время

                - текущее время темы)

                и игнорируя текущую тему весомую сумму

                * /

                T[i][j] = max(marksarr[i]

                                  + T[i - 1][j - timearr[i]],

                              T[i - 1][j]);

            }

        }

    }

  

    // Перемещение вверх в таблице снизу справа

    // рассчитать общее время, затраченное на

    // читаем темы которые можно сделать в

    // данное время и наибольшая весовая сумма

    int i = no_of_topics - 1, j = total_time - 1;

  

    int sum = 0;

  

    while (i > 0 && j > 0) {

  

        // Это означает, что мы не рассматривали

        // читаем эту тему для

        // максимальная сумма веса

        if (T[i][j] == T[i - 1][j]) {

  

            i--;

        }

        else {

  

            // Добавляем время темы

            sum += timearr[i];

  

            // Оценка оставшегося времени после

            // учитывая эту текущую тему

            j -= timearr[i];

  

            // Одна тема завершена

            i--;

        }

    }

  

    // Содержит максимальную сумму веса

    // сформирован с учетом тем

    int marks = T[no_of_topics - 1][total_time - 1];

  

    // Условие, когда экзамен не может быть сдан

    if (marks < p)

        return -1;

  

    // Возвращаем метки, которые

    // можно получить после

    // сдача экзамена

    return sum;

}

  
// Код драйвера

int main()

{

    // Количество тем, осталось часов

    // и проходные баллы

    int n = 4, h = 10, p = 10;

  

    // n + 1 берется для простоты в циклах

    // Массив будет проиндексирован, начиная с 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 реализация подхода

import java.io.*;

  

class GFG

{

      
// Функция для возврата максимальных оценок
// рассматривая темы, которые могут быть
// завершено в заданный промежуток времени

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];

  

    // Инициализация

  

    // Если нам дано 0 раз

    // тогда ничего не поделаешь

    // Значит, все значения равны 0

    for (int i = 0; i < no_of_topics; i++) 

    {

        T[i][0] = 0;

    }

  

    // Если нам дано 0 тем

    // тогда требуемое время

    // наверняка будет 0

    for (int j = 0; j < total_time; j++) 

    {

        T[0][j] = 0;

    }

  

    // Расчет максимальных оценок

    // это может быть достигнуто в

    // заданные временные ограничения

    for (int i = 1; i < no_of_topics; i++) 

    {

  

        for (int j = 1; j < total_time; j++)

        {

  

            // Если время потрачено на чтение этой темы

            // больше времени, оставшегося сейчас на

            // позиция j, тогда не читайте эту тему

            if (j < timearr[i])

            {

  

                T[i][j] = T[i - 1][j];

            }

            else

            {

  

                / * Возникают два случая:

                1) Учитывая текущую тему

                2) Игнорирование текущей темы

                Мы находим максимум (текущая тема вес

                + темы, которые можно сделать в оставшееся время

                - текущее время темы)

                и игнорируя текущую тему весомую сумму

                * /

                T[i][j] = Math.max(marksarr[i]

                                + T[i - 1][j - timearr[i]],

                            T[i - 1][j]);

            }

        }

    }

  

    // Перемещение вверх в таблице снизу справа

    // рассчитать общее время, затраченное на

    // читаем темы которые можно сделать в

    // данное время и наибольшая весовая сумма

    int i = no_of_topics - 1, j = total_time - 1;

  

    int sum = 0;

  

    while (i > 0 && j > 0

    {

  

        // Это означает, что мы не рассматривали

        // читаем эту тему для

        // максимальная сумма веса

        if (T[i][j] == T[i - 1][j])

        {

  

            i--;

        }

        else 

        {

  

            // Добавляем время темы

            sum += timearr[i];

  

            // Оценка оставшегося времени после

            // учитывая эту текущую тему

            j -= timearr[i];

  

            // Одна тема завершена

            i--;

        }

    }

  

    // Содержит максимальную сумму веса

    // сформирован с учетом тем

    int marks = T[no_of_topics - 1][total_time - 1];

  

    // Условие, когда экзамен не может быть сдан

    if (marks < p)

        return -1;

  

    // Возвращаем метки, которые

    // можно получить после

    // сдача экзамена

    return sum;

}

  

    // Код драйвера

    public static void main (String[] args) 

    {

        // Количество тем, осталось часов

        // и проходные баллы

        int n = 4, h = 10, p = 10;

      

        // n + 1 берется для простоты в циклах

        // Массив будет проиндексирован, начиная с 1

        int marksarr[] = { 0, 6, 4, 2, 8 };

        int timearr[] = { 0, 4, 6, 2, 7 };

      

        System.out.println( MaximumMarks(marksarr, timearr, h, n, p));

    }

}

  
// Этот код предоставлен vt_m

python3

# Python3 реализация подхода

import numpy as np

  
# Функция возврата максимальных оценок
# рассматривая темы, которые могут быть
# выполнено за заданное время

def MaximumMarks(marksarr, timearr, h, n, p) : 

  

    no_of_topics = n + 1

    total_time = h + 1

  

    T = np.zeros((no_of_topics, total_time)); 

  

    # Инициализация

  

    # Если нам дадут 0 раз

    # тогда ничего не поделаешь

    # Так что все значения равны 0

    for i in range(no_of_topics) : 

        T[i][0] = 0

      

    # Если нам дают 0 тем

    # тогда необходимое время

    # будет 0 наверняка

    for j in range(total_time) : 

        T[0][j] = 0

      

    # Расчет максимальной оценки

    # что может быть достигнуто под

    # заданные временные ограничения

    for i in range(1, no_of_topics) : 

  

        for j in range(1, total_time) : 

  

            # Если время заняло, чтобы прочитать эту тему

            # больше времени, оставшегося сейчас на

            # позиция j, тогда не читайте эту тему

            if (j < timearr[i]) :

  

                T[i][j] = T[i - 1][j]; 

              

            else :

  

                "" "Возникают два случая:

                1) Учитывая текущую тему

                2) Игнорирование текущей темы

                Мы находим максимум (текущая тема вес

                + темы, которые можно сделать в оставшееся время

                - текущее время темы)

                и игнорируя текущую тему весомую сумму

                «»»

                T[i][j] = max(marksarr[i] + 

                              T[i - 1][j - timearr[i]], 

                              T[i - 1][j]); 

  

    # Перемещение вверх в таблице снизу справа

    # для расчета общего времени, затраченного на

    # читать темы, которые можно сделать в

    # данное время и максимальная сумма веса

    i = no_of_topics - 1; j = total_time - 1

  

    sum = 0

  

    while (i > 0 and j > 0) : 

  

        # Это означает, что мы не учли

        # чтение этой темы для

        # максимальная сумма веса

        if (T[i][j] == T[i - 1][j]) :

  

            i -= 1

          

        else

  

            # Добавление времени темы

            sum += timearr[i]; 

  

            # Оценка левого со временем после

            # учитывая эту текущую тему

            j -= timearr[i]; 

  

            # Одна тема завершена

            i -= 1

  

    # Содержит максимальную сумму веса

    # сформирован с учетом темы

    marks = T[no_of_topics - 1][total_time - 1]; 

  

    # Условие, когда экзамен не может быть сдан

    if (marks < p) :

        return -1

  

    # Вернуть отметки, которые

    # можно получить после

    # сдача экзамена

    return sum

  
# Код драйвера

if __name__ == "__main__"

  

    # Количество тем, осталось часов

    # и проходные баллы

    n = 4; h = 10; p = 10;

      

    # n + 1 берется для простоты в циклах

    # Массив будет проиндексирован, начиная с 1

    marksarr = [ 0, 6, 4, 2, 8 ]; 

    timearr = [ 0, 4, 6, 2, 7 ]; 

      

    print(MaximumMarks(marksarr, timearr, h, n, p)); 

  
# Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System; 

      

class GFG

{

      
// Функция для возврата максимальных оценок
// рассматривая темы, которые могут быть
// завершено в заданный промежуток времени

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;

    // Инициализация

  

    // Если нам дано 0 раз

    // тогда ничего не поделаешь

    // Значит, все значения равны 0

    for (i = 0; i < no_of_topics; i++) 

    {

        T[i, 0] = 0;

    }

  

    // Если нам дано 0 тем

    // тогда требуемое время

    // наверняка будет 0

    for (j = 0; j < total_time; j++) 

    {

        T[0, j] = 0;

    }

  

    // Расчет максимальных оценок

    // это может быть достигнуто в

    // заданные временные ограничения

    for (i = 1; i < no_of_topics; i++) 

    {

  

        for (j = 1; j < total_time; j++)

        {

  

            // Если время потрачено на чтение этой темы

            // больше времени, оставшегося сейчас на

            // позиция j, тогда не читайте эту тему

            if (j < timearr[i])

            {

  

                T[i, j] = T[i - 1, j];

            }

            else

            {

  

                / * Возникают два случая:

                1) Учитывая текущую тему

                2) Игнорирование текущей темы

                Мы находим максимум (текущая тема вес

                + темы, которые можно сделать в оставшееся время

                - текущее время темы)

                и игнорируя текущую тему весомую сумму

                * /

                T[i, j] = Math.Max(marksarr[i]

                                + T[i - 1, j - timearr[i]],

                            T[i - 1, j]);

            }

        }

    }

  

    // Перемещение вверх в таблице снизу справа

    // рассчитать общее время, затраченное на

    // читаем темы которые можно сделать в

    // данное время и наибольшая весовая сумма

    i = no_of_topics - 1; j = total_time - 1;

  

    int sum = 0;

  

    while (i > 0 && j > 0) 

    {

  

        // Это означает, что мы не рассматривали

        // читаем эту тему для

        // максимальная сумма веса

        if (T[i, j] == T[i - 1, j])

        {

  

            i--;

        }

        else

        {

  

            // Добавляем время темы

            sum += timearr[i];

  

            // Оценка оставшегося времени после

            // учитывая эту текущую тему

            j -= timearr[i];

  

            // Одна тема завершена

            i--;

        }

    }

  

    // Содержит максимальную сумму веса

    // сформирован с учетом тем

    int marks = T[no_of_topics - 1, total_time - 1];

  

    // Условие, когда экзамен не может быть сдан

    if (marks < p)

        return -1;

  

    // Возвращаем метки, которые

    // можно получить после

    // сдача экзамена

    return sum;

}

  

    // Код драйвера

    public static void Main (String[] args) 

    {

        // Количество тем, осталось часов

        // и проходные баллы

        int n = 4, h = 10, p = 10;

      

        // n + 1 берется для простоты в циклах

        // Массив будет проиндексирован, начиная с 1

        int []marksarr = { 0, 6, 4, 2, 8 };

        int []timearr = { 0, 4, 6, 2, 7 };

      

        Console.WriteLine( MaximumMarks(marksarr, timearr, h, n, p));

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

Выход:

10

Рекомендуемые посты:

Найдите максимум тем для подготовки к сдаче экзамена

0.00 (0%) 0 votes