Με συγχωρείτε για τη μεγάλη καθυστέρηση. Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Σεπτέμβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Στο πρόβλημα μας δίνονται 2 διαφορετικοί τύποι αντικειμένων. Για τον κάθε τύπο γνωρίζουμε την αξία του και το βάρος του. Έχουμε μία τσάντα που αντέχει το πολύ Χ κιλά αντικειμένων, και θέλουμε να μεγιστοποιήσουμε την αξία των αντικειμένων που θα βάλουμε στην τσάντα.
Υποθέστε ότι το Χ θα είναι το πολύ 250.
Link για το πρόβλημα: https://www.spoj.com/problems/ZTC/
Στις 20 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου όμως αν το ξεχάσω.
Καλή επιτυχία!
Μηνιαία Πρόκληση: Σεπτέμβριος 2020
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Μηνιαία Πρόκληση: Σεπτέμβριος 2020
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Σεπτέμβριος 2020
Σκεφτείτε ότι χωρίζουμε τα αντικείμενα σε φυσιολογικά και σε τεράστια. Θα λέμε φυσιολογικά αυτά που έχουν βάρος μικρότερο από Τ, και τεράστια τα υπόλοιπα. Το Τ δεν είναι κάτι που μας δίνεται, αλλά κάτι που αποφασίζουμε εμείς. Θα συνεχίσω όμως να το λέω Τ για να μη μπλέκουμε με νούμερα.
Αν υποθέσουμε ότι ένα από τα δύο αντικείμενα είναι τεράστιο, τότε υπάρχει αλγόριθμος που τρέχει σε χρόνο O(X/T).
Αν κανένα από τα δύο αντικείμενα δεν είναι τεράστιο, τότε υπάρχει αλγόριθμος που τρέχει σε χρόνο Ο(Τ).
Επιλέγοντας έξυπνα την τιμή του Τ, μπορούμε να συνδυάσουμε τους δύο παραπάνω αλγορίθμους ώστε να έχουμε πάντα ικανοποιητική πολυπλοκότητα.
Αν υποθέσουμε ότι ένα από τα δύο αντικείμενα είναι τεράστιο, τότε υπάρχει αλγόριθμος που τρέχει σε χρόνο O(X/T).
Αν κανένα από τα δύο αντικείμενα δεν είναι τεράστιο, τότε υπάρχει αλγόριθμος που τρέχει σε χρόνο Ο(Τ).
Επιλέγοντας έξυπνα την τιμή του Τ, μπορούμε να συνδυάσουμε τους δύο παραπάνω αλγορίθμους ώστε να έχουμε πάντα ικανοποιητική πολυπλοκότητα.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Σεπτέμβριος 2020
Το επόμενο Σάββατο, 3 Οκτωβρίου, στις 18.00 το απόγευμα (ώρα Ελλάδας), θα γίνει η κλήση/συζήτηση για την πρόκληση Σεπτεμβρίου. Στο μεταξύ βεβαίως θα ανέβει η μηνιαία πρόκληση Οκτωβρίου.
Το λινκ της κλήσης: https://ucph-ku.zoom.us/j/64208215479?p ... FmSmxGQT09
Passcode 048093
Κατεβάστε την εφαρμογή γιατί από την online έκδοση υπάρχουν προβλήματα με την προβολή του ασπροπίνακα.
Το λινκ της κλήσης: https://ucph-ku.zoom.us/j/64208215479?p ... FmSmxGQT09
Passcode 048093
Κατεβάστε την εφαρμογή γιατί από την online έκδοση υπάρχουν προβλήματα με την προβολή του ασπροπίνακα.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/