Πρόβλημα με αλγοριθμική άσκηση

[asvos]

Έχω πρόβλημα στην λύση μιας άσκησης. Δεν ξέρω από που να ξεκινήσω πραγματικά.

Μπορεί να είναι πολύ απλή και να σκέφτομαι πολύ σύνθετα δεν ξέρω.

 

Η άσκηση είναι η εξής

 

Διαχειριζόμαστε ενα τηλεπικοινωνιακό δίκτυο το οποίο διαθέτει k σταθμούς βάσης και πρέπει να εξυπηρετήσει n πελάτες, με τους ακόλουθους περιοριορισμούς:

Περιορισμός εμβέλειας: Κάθε πελάτης μπορεί να συνδεθεί με οποιοδήποτε σταθμό βάσης από τον οποίο απέχει το πολύ μια δεδομένη απόσταση r.

Περιορισμός φορτίου: Κάθε σταθμός βάσης μπορεί να εξυπηρετήσει το πολύ L πελάτες.

Σχεδιάστε έναν αποδοτικό αλγόριθμο (πολυωνυμικού χρόνου) που να αποφασίζει αν όλοι οι πελάτες μπορούν να συνδεθούν ταυτόχρονα σε κάποιο σταθμό βάσης χωρίς να παραβιαστουν οι περιορισμοί εμβέλειας και φορτίου.

 

Ελπίζω να το έχω βάλει σε σωστό σημείο το θέμα.

[gtroza]

Διαχειριζόμαστε ενα τηλεπικοινωνιακό δίκτυο το οποίο διαθέτει k σταθμούς βάσης και πρέπει να εξυπηρετήσει n πελάτες, με τους ακόλουθους περιοριορισμούς:

Περιορισμός εμβέλειας: Κάθε πελάτης μπορεί να συνδεθεί με οποιοδήποτε σταθμό βάσης από τον οποίο απέχει το πολύ μια δεδομένη απόσταση r.

Περιορισμός φορτίου: Κάθε σταθμός βάσης μπορεί να εξυπηρετήσει το πολύ L πελάτες.

Σχεδιάστε έναν αποδοτικό αλγόριθμο (πολυωνυμικού χρόνου) που να αποφασίζει αν όλοι οι πελάτες μπορούν να συνδεθούν ταυτόχρονα σε κάποιο σταθμό βάσης χωρίς να παραβιαστουν οι περιορισμοί εμβέλειας και φορτίου.

 

άρα πρέπει να βρείς αν ισχύουν ταυτόχρονα

α. ο αριθμός των πελατών n, να είναι μικρότερος ή ίσος με L

β. και αν υπάρχει ένας τουλάχιστον σταθμός, που η απόστασή του απ' τους πελάτες είναι μικρότερη ή ίση με r

 

ελπίζω να μην σε "παίρνω στο λαιμό μου"!

 

.

[thanos713]

Απ`ότι κατάλαβα, το input θα είναι το L και το r ενός σταθμού και ο αριθμός των πελατών που θέλουν να συνδεθούν με τον σταθμό και η μέγιστη απόστασή τους από τον σταθμό;