Witam, mam napisac poniższy algorytm:
Biuro podróży chce wprowadzić pewne optymalizacje w kosztach podróży.
Podróżni w drodze spędzają czasem wiele dni zatem opłaty za noclegi stanowią poważną część
kosztów podróży. Ze względu na bezpieczeństwo podróży każdy autokar jedzie w ciągu dnia i nie
może przejechać więcej niż 800 kilometrów. Noc na trasie poza końcem i początkiem podróżni i
kierowcy spędzają w hotelach. Podróż trzeba zaplanować optymalnie, żeby liczba noclegów w
ciągu całej wycieczki była jak najmniejsza. Biuro podróży znając potrzebę obniżenia kosztów
wycieczki, postanowiło zbadać czy opłaci się układanie planów podróży tak , aby suma opłat za
noclegi była możliwie najniższa, nawet wtedy gdyby to miało przedłużyć podróż. W każðej ofercie
podana jest odległość hotelu od początku trasy i cena jednostkowa za hotel. Podróżni podróżują
tylko w jedną stronę. Trasa nie ma rozgałęzień. Przez każdy punkt trasy autokar przejeżdża tylko
raz. Nie ma dwóch hoteli w jednym punkcie,wiec każdy hotel może być zidentyfikowany przez
jego odległość od początku trasy. Nie planuje się noclegu ani na początku ani na końcu trasy.
Liczba osób w autobusie nie zmienia się i wszyscy razem z kierowcą płacą taką samą cenę
jednostkową za nocleg w tym samym hotelu. Pojemność hotelu jest tak duża, że wszyscy razem
mogą zanocować w jednym hotelu. Na każdym odcinku trasy o długości 800km jest przynajmniej
jeden hotel, w który można zanocować. Zakładamy, że długość trasy jest liczbą całkowitą
d<=16000, a liczba hoteli h<=1000.
Napisz algorytm, który po wczytaniu długości trasy, liczby hoteli oraz ceny za nocleg w każdy z
hoteli za jedną osobę znajdzie najtańszy plan podróży, tzn. taki, której suma opłat za hotele była jak
najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno rozwiązanie z najmniejszą liczbą
noclegów.
Przykład
Dane:
d=2000
Liczba hoteli h=7
Oferty hoteli posortowane według rosnącej odległości od początku trasy (odległość od początku
trasy i cena za nocleg):
100 54, 120 70, 400 17, 700 38, 1000 25, 1200 18, 1440 40
Wynik:
odległość kolejnych noclegów od początku trasy: 400, 1200
koszt: 35
Stąd moje pytania:
1.Zda się tu algorytm zachłanny? (jeśli tak, to jakie ma mieć kryterium wyboru?)
2. Programowanie dynamiczne? (Na jakie podproblemy to rozbić? Da ktoś wskazówki na zależności rekurencyjne)?
Proszę o jakieś nakierowanie