Рубрики

Оптимальный список чтения для заданного количества дней

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

Пример:

Input:  Number of Days to Finish book = 2
        Number of pages in chapters = {10, 5, 5}
Output: Day 1:  Chapter 1
        Day 2:  Chapters 2 and 3

Input:  Number of Days to Finish book = 3
        Number of pages in chapters = {8, 5, 6, 12}
Output: Day 1:  Chapter 1
        Day 2:  Chapters 2 and 3 
        Day 2:  Chapter 4

Цель состоит в том, чтобы свести к минимуму сумму различий между страницами, читаемыми каждый день, и средним числом страниц. Если среднее число страниц не является целым числом, то оно должно быть округлено до ближайшего целого числа.

В вышеприведенном примере 2 среднее количество страниц составляет (8 + 5 + 6 + 12) / 3 = 31/3, округленное до 10. Таким образом, разница между средним и количеством страниц в день для показанного выше результата составляет « abs (8-10) + abs (5 + 6-10) + abs (12-10) », что равно 5. Значение 5 является оптимальным значением суммы разностей.

Рассмотрим пример 2 выше, где книга состоит из 4 глав со страницами 8, 5, 6 и 12. Пользователь хочет закончить ее через 3 дня. Графическое представление вышеописанного сценария

В приведенном выше графе вершина представляет главу, а ребро e (u, v) представляет количество страниц, которые нужно прочитать, чтобы достичь «v» из «u». Узел раковины добавлен, чтобы символизировать конец книги.

Во-первых, подсчитайте среднее количество страниц для чтения за день (здесь 31/3 примерно 10). Вес нового ребра e '(u, v) будет означать среднюю разницу | avg — e (u, v) |. Модифицированный график для вышеуказанной проблемы будет,

Спасибо Armadillo за инициирование этой мысли в комментарии.

Идея состоит в том, чтобы начать с главы 1 и выполнить DFS, чтобы найти сток с количеством ребер, равным 'k'. Продолжайте хранить посещенные вершины в массиве, скажем 'path []'. Если мы достигаем вершины назначения, а сумма пути меньше, чем оптимальный путь, обновим оптимальное назначение optim_path []. Обратите внимание, что график является DAG, поэтому нет необходимости заботиться о циклах во время DFS.
Ниже приведена реализация той же C ++, матрицы смежности, используемой для представления графа. Следующая программа имеет в основном 4 этапа.
1) Построить ориентированный ациклический граф.
2) Найти оптимальный путь, используя DFS.
3) Распечатать найденный оптимальный путь.

C ++

// C ++ DFS решение для планирования глав для чтения в
// данные дни
# include <iostream>
# include <cstdlib>
# include <climits>
# include <cmath>

using namespace std;

  
// Определяем общее количество глав в книге
// Количество дней, которое пользователь может потратить на чтение
# define CHAPTERS 4
# define DAYS 3
# define NOLINK -1

  
// Массив для хранения окончательного сбалансированного графика

int optimal_path[DAYS+1];

  
// Graph - Node chapter + 1 - приемник, описанный в
// над графиком

int DAG[CHAPTERS+1][CHAPTERS+1];

  
// Обновляет оптимальное назначение с текущим назначением

void updateAssignment(int* path, int path_len);

  
// Основанная на DFS рекурсивная функция для сохранения оптимального пути
// в пути [] размера path_len. Переменная сумма хранит сумму
// всех ребер на текущем пути. k количество дней, проведенных так
// далеко

void assignChapters(int u, int* path, int path_len, int sum, int k)

{

    static int min = INT_MAX;

  

    // Игнорируем присвоение, которое требует больше, чем требуется дней

    if (k < 0)

        return;

  

    // Текущее распределение глав по дням

    path[path_len] = u;

    path_len++;

  

    // Обновляем оптимальное назначение при необходимости

    if (k == 0 && u == CHAPTERS)

    {

        if (sum < min)

        {

            updateAssignment(path, path_len);

            min = sum;

        }

    }

  

    // DFS - Поиск в глубину

    for (int v = u+1; v <= CHAPTERS; v++)

    {

        sum += DAG[u][v];

        assignChapters(v, path, path_len, sum, k-1);

        sum -= DAG[u][v];

    }

}

  
// Эта функция находит и печатает оптимальный список чтения. Сначала создается
// график, затем вызывает метод assignChapters ().

void minAssignment(int pages[])

{

    // 1) ............ КОНСТРУКТИВНЫЙ ГРАФ .................

    // Построение массива частичной суммы S [i] = общее количество страниц

    // до первой главы

    int avg_pages = 0, sum = 0, S[CHAPTERS+1], path[DAYS+1];

    S[0] = 0;

  

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

    {

        sum += pages[i];

        S[i+1] = sum;

    }

  

    // Среднее количество страниц, которые нужно прочитать за день

    avg_pages = round(sum/DAYS);

  

    / * Вершины построения DAG - это название главы &

     * Вес ребра | avg_pages - страницы в главе |

     * Представление матрицы смежности * /

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

    {

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

        {

            if (j <= i)

                DAG[i][j] = NOLINK;

            else

            {

                sum = abs(avg_pages - (S[j] - S[i]));

                DAG[i][j] = sum;

            }

        }

    }

  

    // 2) ............ НАЙТИ ОПТИМАЛЬНЫЙ ПУТЬ ................

    assignChapters(0, path, 0, 0, DAYS);

  

    // 3) ..ПЕЧАТЬ ОПТИМАЛЬНОГО ЧТЕНИЯ С ИСПОЛЬЗОВАНИЕМ ОПТИМАЛЬНОГО ПУТИ ....

    cout << "Optimal Chapter Assignment :" << endl;

    int ch;

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

    {

        ch = optimal_path[i];

        cout << "Day" << i+1 << ": " << ch << " ";

        ch++;

        while ( (i < DAYS-1 && ch < optimal_path[i+1]) ||

                (i == DAYS-1 && ch <= CHAPTERS))

        {

           cout <<  ch << " ";

           ch++;

        }

        cout << endl;

    }

}

  
// Эта функция обновляет optim_path []

void updateAssignment(int* path, int path_len)

{

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

        optimal_path[i] = path[i] + 1;

}

  
// Драйвер программы для проверки расписания

int main(void)

{

    int pages[CHAPTERS] = {7, 5, 6, 12};

  

    // Получить список чтения за заданные дни

    minAssignment(pages);

  

    return 0;

}

python3

# Python3 DFS решение для планирования глав
# для чтения в заданные дни

  
# Рекурсивная функция на основе DFS для хранения
# оптимальный путь в path [] размера path_len.
# Переменная Sum хранит сумму всех ребер на
# текущий путь. k - количество дней, проведенных до сих пор.

def assignChapters(u, path, path_len, Sum, k):

    global CHAPTERS, DAYS, NOLINK, optical_path, DAG, Min

  

    # Игнорировать назначение, которое требует

    # больше, чем требуется дней

    if (k < 0): 

        return

  

    # Текущее распределение глав по дням

    path[path_len] =

    path_len += 1

  

    # Обновите оптимальное назначение при необходимости

    if (k == 0 and u == CHAPTERS):

        if (Sum < Min):

            updateAssignment(path, path_len) 

            Min = Sum

  

    # DFS - Поиск в глубину Поиск раковины

    for v in range(u + 1, CHAPTERS + 1):

        Sum += DAG[u][v] 

        assignChapters(v, path, path_len, Sum, k - 1

        Sum -= DAG[u][v]

  
# Эта функция находит и печатает
# оптимальный список чтения. Сначала создается
# graph, затем вызывает метод assignChapters ().

def MinAssignment(pages):

    global CHAPTERS, DAYS, NOLINK, optical_path, DAG, MIN

      

    # 1) ............ КОНСТРУКТИВНЫЙ ГРАФ .................

    # Построение массива частичной суммы S [i] = общее количество страниц

    # до первой главы

    avg_pages = 0

    Sum = 0 

    S = [None] * (CHAPTERS + 1)

    path = [None] * (DAYS + 1

    S[0] = 0

  

    for i in range(CHAPTERS):

        Sum += pages[i] 

        S[i + 1] = Sum

  

    # Среднее количество страниц, которые нужно прочитать за день

    avg_pages = round(Sum/DAYS) 

  

    # Вершины построения DAG, являющиеся названием главы &

    # Вес ребра | avg_pages - страницы в главе |

    # Представление матрицы смежности

    for i in range(CHAPTERS + 1):

        for j in range(CHAPTERS + 1):

            if (j <= i):

                DAG[i][j] = NOLINK 

            else:

                Sum = abs(avg_pages - (S[j] - S[i])) 

                DAG[i][j] = Sum

  

    # 2) ............ НАЙТИ ОПТИМАЛЬНЫЙ ПУТЬ ................

    assignChapters(0, path, 0, 0, DAYS) 

  

    # 3) .. ПЕРСПЕКТИВНЫЙ ЧИТАТЬ СПИСОК С ИСПОЛЬЗОВАНИЕМ ОПТИМАЛЬНОГО ПУТИ ....

    print("Optimal Chapter Assignment :"

    ch = None

    for i in range(DAYS):

        ch = optimal_path[i] 

        print("Day", i + 1, ": ", ch, end = " "

        ch += 1

        while ((i < DAYS - 1 and ch < optimal_path[i + 1]) or 

               (i == DAYS - 1 and ch <= CHAPTERS)):

            print(ch, end = " "

            ch += 1

        print()

  
# Эта функция обновляет optim_path []

def updateAssignment(path, path_len):

    for i in range(path_len):

        optimal_path[i] = path[i] + 1

  
Код водителя

  
# Определить общее количество глав в книге
# Количество дней, которое пользователь может потратить на чтение

CHAPTERS = 4

DAYS = 3

NOLINK = -1

  
# Массив для хранения окончательного сбалансированного графика

optimal_path = [None] * (DAYS + 1)

  
# График - Узел главы + 1 это раковина
# описано на приведенном выше графике

DAG = [[None] * (CHAPTERS + 1

       for i in range(CHAPTERS + 1)] 

  

Min = 999999999999

pages = [7, 5, 6, 12

  
# Получить список чтения за заданные дни
MinAssignment(pages)

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

Выход:

 
Optimal Chapter Assignment :
Day1: 1
Day2: 2 3
Day3: 4

Эта статья предоставлена Balaji S. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Оптимальный список чтения для заданного количества дней

0.00 (0%) 0 votes