Μηνιαία Πρόκληση: Σεπτέμβριος 2020

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Μηνιαία Πρόκληση: Σεπτέμβριος 2020

Δημοσίευση από Κηπουρίδης »

Με συγχωρείτε για τη μεγάλη καθυστέρηση. Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Σεπτέμβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.

Στο πρόβλημα μας δίνονται 2 διαφορετικοί τύποι αντικειμένων. Για τον κάθε τύπο γνωρίζουμε την αξία του και το βάρος του. Έχουμε μία τσάντα που αντέχει το πολύ Χ κιλά αντικειμένων, και θέλουμε να μεγιστοποιήσουμε την αξία των αντικειμένων που θα βάλουμε στην τσάντα.

Υποθέστε ότι το Χ θα είναι το πολύ 250.

Link για το πρόβλημα: https://www.spoj.com/problems/ZTC/

Στις 20 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου όμως αν το ξεχάσω.

Καλή επιτυχία!
Λύσεις θεμάτων ΠΔΠ: 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/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Μηνιαία Πρόκληση: Σεπτέμβριος 2020

Δημοσίευση από Κηπουρίδης »

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

Αν υποθέσουμε ότι ένα από τα δύο αντικείμενα είναι τεράστιο, τότε υπάρχει αλγόριθμος που τρέχει σε χρόνο 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/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Μηνιαία Πρόκληση: Σεπτέμβριος 2020

Δημοσίευση από Κηπουρίδης »

Το επόμενο Σάββατο, 3 Οκτωβρίου, στις 18.00 το απόγευμα (ώρα Ελλάδας), θα γίνει η κλήση/συζήτηση για την πρόκληση Σεπτεμβρίου. Στο μεταξύ βεβαίως θα ανέβει η μηνιαία πρόκληση Οκτωβρίου.

Το λινκ της κλήσης: 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/
Απάντηση