Dynamic Programming

[Chrisgs]

Heya,

 

Εδώ και κάτι μέρες προσπαθώ να μάθω για τον δυναμικό προγραμματισμό,αλλά όσα και να έχω διαβάσει μου ψιλο φαίνονται περίπλοκα.Ενώ σε όσα προβλήματα έχω διαβάσει μπορώ να καταλάβω πλήρως το πως βγαίνει ο τύπος της λύσης, όταν πάω να κάνω κάτι μόνος μου σκαλώνω τελείως.Έχετε κάποιο tip για το πως να διαβάζω/σκέφτομαι ένα πρόβλημα?Νιώθω ότι είμαι πολύ κοντά στο να το καταλάβω πλήρως,απλώς μου λείπει μια μικρή λεπτομέρεια στο σκεπτικό (νομίζω δηλαδή)

 

Ευχαριστω! 

[defacer]

Ποιός "τύπος της λύσης"; Ο δυναμικός προγραμματισμός δεν είναι τυφλοσούρτης, είναι προσέγγιση. Τι ακριβώς έχεις διαβάσει δηλαδή και τι προσπαθείς να κάνεις; Έχεις δει κάποια άσκηση που να καταλαβαίνεις, πχ ένα δυναμικό υπολογισμό Fibonacci?

[Chrisgs]

Το γνωρίζω ότι δεν είναι τυφλοσουρτης. Όταν λέω τύπο της λύσης εννοώ ότι όταν βλέπω να λύνουμε τέτοια πρόβληματα, σε μια φάση βγάζουν συνήθως έναν τύπο της μορφής OPT = max(....) ή κάτι παρόμοιο ο οποίος τυπικά είναι η μορφή του αλγόριθμου. Ελπίζω να μην σε έμπλεξα όπως τα είπα

 

Επίσης έχω ένα πρόβλημα αλλά δεν μπορώ να το στείλω προς το παρόν γιατί δεν είμαι σπίτι

[defacer]

Δεν έχω την παραμικρή ιδέα τι προσπαθείς να πεις. "Βγάζουν συνήθως ένα τύπο"; Ποιοί βγάζουν, τι πάει να πει συνήθως και τι κάνει αυτός ο τύπος; Δεν έχω συναντήσει ποτέ μου κανένα τύπο που να είναι σχετικός συγκεκριμένα επειδή κάτι είχε να κάνει με δυναμικό προγραμματισμό.

 

Ακούγεται σα να έχεις πάρει τελείως λάθος πορεία.

[Chrisgs]

Hmm...μήπως βοηθάει αυτό?

 

 

Όταν λέω τύπο αυτό εννοώ.

Γενικά πιστεύω μπορώ να βρω υποπροβλήματα αλλά κολλάω στο κομμάτι του κώδικα κυρίως.

 

(Λογικά αυτό για την λάθος πορεία ισχύει, αλλά δεν το'χα καταλάβει μέχρι τώρα)

[defacer]

Αυτοί οι τύποι είναι απλώς ένας μαθηματικός (σύντομος) τρόπος να εκφράσεις το προφανές: αν ξέρεις το βέλτιστο τρόπο για να γεμίσεις ένα σακίδιο π.χ. 10 κιλών και μέσα στα υπόλοιπα πράγματα που διαθέτεις είναι ένα καρπούζι 5 κιλών, προφανώς ξέρεις και το βέλτιστο τρόπο να γεμίσεις ένα σακίδιο 15 κιλών: βάζεις μέσα ο,τι θα έβαζες για τα 10, συν το καρπούζι. Δεν πρόκειται να ξεκινήσεις από αυτόν τον τύπο και να γράψεις πρόγραμμα, δε δουλεύουν έτσι τα πράγματα.

 

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

 

Άποψή μου, άστα όλα αυτά στην άκρη και κάνε ένα δυναμικό fibonacci που είναι πρακτικά το απλούστερο δυνατό (μιλάμε για 3 λεπτά υπόθεση αν ξέρεις τι κάνεις) να μπεις στο πνεύμα χωρίς να μπερδεύεσαι με τύπους. Επίσης, "dynamic programming fibonacci" πρέπει να σου βγάλει περίπου 7 δισεκατομμύρια results στο google αν κολλήσεις.

[Chrisgs]

Το'χα παρει τελειως λαθος τελικα.Νομιζα οτι οολη η δουλεια γινοταν για να βγει αυτος ο τυπος και οτι αν δεν τον εβγαζες δεν μπορεις να γραψεις το προβλημα,θα τσεκαρω το φιμπονατσι αν ειναι κ διαφορα αλλα πραγματα π βρηκα.Ευχαριστω πολυ φιλε μου!