Asignar número mínimo de páginas (no consecutivas)

Dada la cantidad de páginas en N libros diferentes y M alumnos. A cada alumno se le asigna la lectura de unos libros que pueden ser consecutivos o no consecutivos. La tarea es asignar libros de manera que el número máximo de páginas asignadas a un alumno sea el mínimo. 

Ejemplos: 

Entrada : páginas = {8, 15, 10, 20, 8}, M = 2
Salida: 31
Explicación: una distribución óptima es [8, 15, 8] y [10, 20]

• El primer estudiante recibe [8, 15, 8] que tiene un total de 8 + 15 + 8 = 31 páginas.
• El segundo estudiante recibe [10, 20] que tiene un total de 10 + 20 = 30 páginas.
• La distribución es max(31, 30) = 31.

Se puede demostrar que no hay distribución con número máximo de páginas inferior a 31.

Entrada: páginas = {6, 1, 3, 2, 2, 4, 1, 2}, M = 3
Salida: 7
Explicación: una distribución óptima es [6, 1], [3, 2, 2] y [ 4, 1, 2]

• El primer estudiante recibe [6, 1] que tiene un total de 6 + 1 = 7 páginas.
• El segundo estudiante recibe [3, 2, 2] que tiene un total de 3 + 2 + 2 = 7 páginas.
• El tercer estudiante recibe [4, 1, 2] que tiene un total de 4 + 1 + 2 = 7 páginas.
• La distribución es max(7, 7, 7) = 7.

Se puede demostrar que no hay un número máximo de páginas de distribución inferior a 7.

Enfoque: El problema se puede resolver en base al concepto de retroceso :

Para cada libro hay dos opciones.

• Dar un libro a un estudiante y sumar el número de páginas para ese estudiante
• Salta a ese estudiante y dale el libro a otro estudiante. 

Una vez asignados todos los libros 

• Encuentre el número máximo de páginas asignadas para un estudiante en cada caso y 
• Almacenar el mínimo entre la asignación máxima

Siga los pasos dados para resolver el problema utilizando el enfoque anterior:

• Recursivamente para cada libro: 
  • Recorra a cada estudiante y asígnele el libro o pase al siguiente estudiante.
• Una vez repartidos todos los libros,  
  • Calcular el número máximo de páginas asignadas a un alumno y 
  • Devuelve el mínimo del máximo actual y la respuesta calculada en los pasos anteriores 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
int ans = INT_MAX;
vector<int> students;
 
// Function to minimize the maximum number of pages
void rec(int i, int N, vector<int>& pages, int M)
{
    if (i == N) {
 
        // If all books are included then find
        // the maximum no of pages for any
        // student store minimum among
        // the maximum
        ans = min(ans, *max_element(students.begin(),
                                    students.end()));
        return;
    }
 
    // ith book can go in any of the students
    for (int j = 0; j < M; ++j) {
 
        // Include the book for jth student
        students[j] += pages[i];
 
        // Recursively call for the next book
        rec(i + 1, N, pages, M);
 
        // If the ith book is not included for jth student
        students[j] -= pages[i];
    }
}
 
// Driver's code
int main()
{
    vector<int> pages = { 8, 15, 10, 20, 8 };
    int M = 2;
    students.assign(M, 0);
 
    // Function call
    rec(0, pages.size(), pages, M);
    cout << ans << endl;
    return 0;
}

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    static int ans = Integer.MAX_VALUE;
    static int[] students = new int[2];
 
    // Function to minimize the maximum number of pages
    static void rec(int i, int N, int[] pages, int M)
    {
        if (i == N) {
            // If all books are included then find the
            // maximum no of pages for any student store
            // minimum among the maximum
            ans = Math.min(
                ans,
                Arrays.stream(students).max().getAsInt());
            return;
        }
 
        // ith book can go in any of the students
        for (int j = 0; j < M; j++) {
 
            // Include the book for jth student
            students[j] += pages[i];
 
            // Recursively call for the next book
            rec(i + 1, N, pages, M);
 
            // If the ith book is not included for jth
            // student
            students[j] -= pages[i];
        }
    }
 
    public static void main(String[] args)
    {
        int[] pages = { 8, 15, 10, 20, 8 };
        int M = 2;
 
        // Function call
        rec(0, pages.length, pages, M);
 
        System.out.print(ans);
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

<script>
    // JavaScript program for the above approach
 
    let ans = 2147483647;
    let students = [];
 
    // Function to minimize the maximum number of pages
    const rec = (i, N, pages, M) => {
        if (i == N) {
 
            // If all books are included then find
            // the maximum no of pages for any
            // student store minimum among
            // the maximum
            ans = Math.min(ans, Math.max(...students));
            return;
        }
 
        // ith book can go in any of the students
        for (let j = 0; j < M; ++j) {
 
            // Include the book for jth student
            students[j] += pages[i];
 
            // Recursively call for the next book
            rec(i + 1, N, pages, M);
 
            // If the ith book is not included for jth student
            students[j] -= pages[i];
        }
    }
 
    // Driver's code
 
    let pages = [8, 15, 10, 20, 8];
    let M = 2;
    students = new Array(M).fill(0);
 
    // Function call
    rec(0, pages.length, pages, M);
    document.write(ans);
 
    // This code is contributed by rakeshsahni
 
</script>

Minimum no of pages: 31

Complejidad de Tiempo: O(M * M ^N )
Espacio Auxiliar: O(1)