Dzięki user3125280, D.W. i Evgeny Kluev pytanie zostało zaktualizowane.

Mam listę stron internetowych i muszę je często pobierać, każda strona ma inną częstotliwość pobierania. Na podstawie tej częstotliwości grupujemy strony internetowe w 5 grupach:

Items in group 1 are downloaded once per 1 hour
items in group 2 once per 2 hours
items in group 3 once per 4 hours
items in group 4 once per 12 hours
items in group 5 once per 24 hours

Oznacza to, że musimy pobrać wszystkie strony grupy 1 w ciągu 1 godziny, całą grupę 2 w ciągu 2 godzin itd.

Próbuję stworzyć algorytm. Jako dane wejściowe mam:

za)DATA_ARR = jedna tablica z 5 liczbami. Każda liczba reprezentuje liczbę elementów w tej grupie.

b)TIME_ARR = jedna tablica z 5 liczbami (1, 2, 4, 12, 24) reprezentująca częstotliwość pobierania elementów.

b)X = całkowita liczba stron do pobrania na godzinę. Jest to obliczane za pomocą item_in_group / download_frequently i zaokrąglane w górę.If we have 15 items in group 5, and 3 items in group 4, this will be 15/24 + 3/12 = 0.875 and rounded is 1.

Co godzinę mój program musi się pobrać pod maxX witryn. Spodziewam się, że algorytm wyświetli coś takiego:

Hour 1: A1 B0 C4 D5
Hour 2: A2 B1 C2 D2
...

A1 = 2 pozycja pierwszej grupy
C0 = 1 pozycja trzeciej grupy

Mój algorytm musi być jak najbardziej wydajny. To znaczy:

a) wzór musi byćrozszerzalny do co najmniej 200 godzin
b)nie ma potrzeby tworzenia powtarzalnego wzoru
c) spacje sąpotrzebne kiedy to możliwe, aby wykorzystać absolutną minimalną przepustowość
re)nigdy nie pobieraj elementu częściej niż częstotliwość aktualizacji, bez wyjątków

Przykład:

group 1: 0 items | once per 1 hour
group 2: 3 items | once per 2 hours
group 3: 4 items | once per 4 hours
group 4: 0 items | once per 12 hours
group 5: 0 items | once per 24 hours

Obliczamy liczbę przedmiotów, które możemy zabrać na godzinę:3/2+4/4 = 2.5. We round this upwards and it's 3.

Za pomocą ołówka i papieru możemy znaleźć następujące rozwiązanie:

Hour 1: B0 C0 B1
Hour 2: B2 C1 c2
Hour 3: B0 C3 B1
Hour 4: B2
Hour 5: B0 C0 B1
Hour 6: B2 C1 c2
Hour 7: B0 C3 B1
Hour 8: B2
Hour 9: B0 C0 B1
Hour 10: B2 C1 c2
Hour 11: B0 C3 B1
Hour 12: B2
Hour 13: B0 C0 B1
Hour 14: B2 C1 c2
and continue the above.

BierzemyC0, C1 C2, iC3 raz na 4 godziny. Bierzemy teżB0, B1 iB2 raz na 2 godziny.

Pytanie: Proszę mi wyjaśnić, w jaki sposób zaprojektować algorytm, który będzie w stanie pobrać przedmioty, korzystając z absolutnej minimalnej liczby pobrań? Brute force toNIE rozwiązanie i algorytm muszą być wydajne pod względem CPU, ponieważ liczba elementów może być ogromna.

Możesz przeczytać odpowiedź zamieszczoną tutaj:https://cs.stackexchange.com/a/19422/12497 a także odpowiedź zamieszczona poniżej przez użytkownika3125280.