Μερικές ιδέες

[Dimitris]

Και ιδού μια πρώτη εκδοχή του άρθρου:

Spoiler: show

Tις προάλλες μιλούσα με ένα φίλο προγραμματιστή και διαρρήκτη (όχι εγώ δεν είμαι διαρρήκτης) και μου εξηγούσε πως από τα πιο δύσκολα προβλήματα στον προγραμματισμό είναι αυτά που εμφανίζονται στην καθημερινή απασχόληση ενός διαρρήκτη. Τι θέλω να πω; Ένας διαρρήκτης θα είχε προφανώς ένα σακίδιο στον ώμο του και θα ήθελε να το γεμίσει με ό,τι πολύτιμο βρεί. Αλλά τον περιορίζει το βάρος που μπορεί να σηκώσει ώστε να είναι ικανός να την κάνει γρήγορα. Ταυτόχρονα όμως μερικά βαριά αντικείμενα είναι και πολύτιμα ενώ μερικά ελαφριά δεν αξίζουν και πολύ. Πως θα αποφασίσει τι πρέπει να βάλει στο σάκο του και τί όχι; Και δεν έχει φυσικά όλη τη νύχτα μπροστά του, όσο πιο πολύ αργεί τόσο αυξάνεται ο κίνδυνος να τον εντοπίσουν. Αν ήξερε δυναμικό προγραμματισμό η λύση του προβλήματος θα ήταν παιχνιδάκι

Ας υποθέσουμε ότι μπορεί να σηκώσει 15 κιλά και έχει τα εξής 5 αντικείμενα για να επιλέξει:
σύγχρονο ηλεκτρονικό υπολογιστή αξίας 1.000 ευρώ, 1 κιλό
επίχρυση ταμπακέρα αξίας 2.000 ευρώ, 1 κιλό
φθηνό κινέζικο βάζο αξίας 2.000 ευρώ, 2 κιλά
πλάκες χρυσού αξίας 4.000 ευρώ, 12 κιλά
πίνακας ζωγραφικής αξίας 10.000 ευρώ, 4 κιλά

Εσείς ποια αντικείμενα θα παίρνατε; Σιγουρα τις πλάκες χρυσού και τον πίνακα ζωγραφικής αλλά δυστυχώς υπερβαίνουν το όριο των 15 κιλών. Mε μία δεύτερη σκέψη βλέπουμε ότι συμφέρει να πάρουμε τον πίνακα ζωγραφικής, την ταμπακέρα και το κινέζικο βάζο συνολικής αξίας 14.000 ευρώ και 8 κιλά μόλις. Αλλά πως είμαστε σίγουροι ότι ελέγξαμε όλους τους πιθανούς συνδυασμούς; Ας δούμε πως σκέφτεται ο διαρρήκτης μας.

Φυσικά όλους αυτούς τους υπολογισμούς τους έκανε στο netbook που κουβαλάει πάντα μαζί του και έχει προγραμματίσει τέτοιες εφαρμογές για τις δύσκολες στιγμές.

ΥΓ. Δεν έχω καμία σχέση με διαρρήκτες ή κλοπιμαία αντικείμενα

Πώς σας φαίνεται;

[kalakouentin]

Γραμμικός προγραμματισμός μου φαίνεται.
Θα δώσουμε και την απάντηση σε AMPL ή GAMS? Γιατί κανένα από τα 2 δεν είναι και Open Source.
(sorry δε μπορούσα να συγκρατηθώ)

Νομίζω ότι καλύτερο (και πιο συναφές) προγραμματιστικά είναι να έχουμε κάποιο πιο computer oriented problem. Σε φάση να μειώσουν το big_O requirement σε μνήμη ή χρόνο κάποιου προγράμματος. (of the top of my head, Δίνουμε πχ. έναν κακογραμμένο Knuth-Morris-Pratt algorithm ή έναν Boyer-Moore και τους ζητάμε να τον διορθώσουν).
Εγώ απλά συνεισφέρω τη γνώμη μου, δεν έχω χρόνο να υλοποιήσω κάτι τέτοιο, απλά αυτό το πρόβλημα που προτάθηκε, δε μου γέμισε και πολύ σοβαρά το μάτι υπολογιστικά.... Ένα μάθημα Operational Research να έχει κάνει ο άλλος και ας μην ξέρει πώς να ανοίξει υπολογιστή, και το βγάζει.

(Μην πω τώρα ότι αν είναι καήλης, μπορεί να το ρίξει στο χαρτί και να το λύσει ψάχνοντας για τους Lagrange multipliers - με πολύ ελεύθερο χρόνο)

[Dimitris]

Καλά ντε μη βαράς είπα να ξεκινήσω με κάτι απλό. Αν σας φαίνεται πολύ εύκολο μπορώ να βάλω και πιο δύσκολα.

ΥΓ. Το συγκεκριμένο πρόβλημα λύνεται με 20 αντε 30 γραμμές python

Πιο συγκεκριμένα το πρόβλημα αυτό είναι γνωστό ως knapsack problem και οι γενικεύσεις του περιλαμβάνουν αρκετά δύσκολα προβλήματα "πακεταρίσματος" και η λύση τους βασίζεται στην αρχή Bellman.

http://en.wikipedia.org/wiki/Knapsack_problem
http://en.wikipedia.org/wiki/Bellman_equation

[sudobash]

Εξαιρετική ιδέα να μπει ενότητα με προγραμματιστικούς γρίφους!!

Μια πρόταση: το πρόβλημα των n-queens (γενίκευση του eight queens puzzle). Να δοθεί ένας έτοιμος κώδικας με αλγόριθμο όχι τόσο καλό που να λύνει για μικρό αριθμό τετραγώνων και να προσπαθήσει κάποιος να αυξήσει τον αριθμό αυτό.