Optymalny sposób na przeczytanie książki zawierającej N rozdziałów w dniach M

Question

Natknąłem się na to pytanie z wywiadu: Biorąc pod uwagę książkę z N rozdziałami (każdy rozdział ma oczywiście inną liczbę stron), jaki jest optymalny sposób na ukończenie całej książki w M dniach z ograniczeniem, że rozdział musi być przeczytany całkowicie w tym samym dniu.

Przykład:

Chapters[] = {7, 5, 3, 9, 10} 
Days = 4 

Trzeba czytać:

Chapter1 on Day1, Chapters2 and Chapter3 on Day2, Chapter4 on Day3 i Chapter5 on Day4.

Rozumiem, że należy dążyć do zminimalizowania sumy bezwzględnych różnic całkowitej liczby przeczytanych stron ze średnią liczbą stron, które najlepiej "przeczytać" jednego dnia. Nie jestem jednak w stanie przetłumaczyć tego pomysłu na strukturę danych i algorytm. Każdy inny pomysł lub dane wejściowe są doceniane.

Answer 1

Można użyć programowania dynamicznego.

1. Średnia jest równa totalNumberOfPages/numberOfDays i nie zależy od sposobu, w jaki czytamy książkę.

2. Stan jest (liczba rozdziałów, które skończymy, liczba dni, które już wydaliśmy). Wartość stanu jest jak dotąd minimalną sumą różnic bezwzględnych.

3. Podstawowy przypadek, jeśli f(0, 0) = 0.

4. Przejścia są następujące:

   • Załóżmy, że obecny stan jest (chapters, days).

   • Możemy iteracyjne nad liczbą rozdziałach będziemy czytać następnego dnia (będę go add nazwać) i wprowadzić następujące przejścia: f(chapters + add, days + 1) = min(f(chapters + add, days + 1), f(chapters, days) + abs(average - the number of pages in chapter + 1 ... chapter + add chapters).

5. Odpowiedź jest f(totalNumberOfChapters, totalNumberOfDays).

Rozwiązanie to opiera się na założeniu, że naszym celem jest „zminimalizować sumę bezwzględnych różnic sumy stron czytać ze średniej liczby stron, które powinno się«doskonale»czytać na jeden dzień”.

Ale jeśli w opisie problemu nie podano, jakie jest kryterium optymalności, sugerowałbym zminimalizowanie maksymalnej liczby stron czytanych w ciągu jednego dnia (moim zdaniem cel, który nie jest zbyt dobrze czytany z rzędu, ma więcej sensu). W tym przypadku istnieje prostsze i wydajniejsze rozwiązanie: możemy wyszukiwać binarnie w odpowiedzi i używać chciwego algorytmu, aby sprawdzić, czy ustalony kandydat jest wykonalny.