Knapsack

[Dimitris]

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

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

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

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

Kαι ξεκινώντας από αυτό το πρόβλημα είπα να μεταγράψω τον κώδικα που έχω από fortran (και λίγη C) στην πολλά συζητούμενη python. Eπειδή όμως η βιβλιοθηκή αυτή περιέχει κώδικα από διάφορες εφαρμογές είπα να την ονομάσω knapsack. Είναι ακόμη σε alpha στάδια (δηλαδή δεν την έχω τεστάρει καθόλου) οπότε μη δοκιμάσετε να τη χρησιμοποιήσετε για να λύσετε προβλήματα, πριν δοκιμάσετε ότι λειτουργεί όπως θέλετε.

Περιλαμβάνει προς στιγμή:
blend.py: Μερικές blending functions για παρεμβολή.
count.py: Mετράει, αφαιρεί, ταξινομεί στοιχεία σε μια λίστα.
geometry.py: Υπολογιστική γεωμετρια, Bezier curves, splines, κλπ.
grid.py: Δημιουργία πλέγματος.
knapsack.py: Ό,τι δεν ταίριαζε αλλού, μαζί με έναν αλγόριθμο για τη λύση του παραπάνω προβλήματος.
matrix.py: Μερικές συναρτήσεις που δε βρήκα στο numpy.
multiscale.py: Συναρτήσεις χρήσιμες για αναπαράσταση σε πολλαπλές κλίμακες.
spectrum.py: Συναρτήσεις που αναπαριστούν φάσματα.
util.py: Δυο χρήσιμες συναρτήσεις.

Όπως είπα καθε άλλο παρά έτοιμη είναι, αλλά είπα να κάνω την αρχή. Και φυσικά υπό τη BSD (3-clause) άδεια.

Και ο σύνδεσμος φυσικά:
http://rapidshare.com/files/276773576/k ... ar.gz.html

Στο μέλλον όταν ωριμάσει θα δημιουργηθεί cvs repository στο sourceforge.

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

[simosx]

Πολύ καλή δουλειά.

Ίσως είναι καλύτερο να βάλεις τα αρχεία σε κάποιο VCS (version control system), ώστε να είναι εφικτή η παρακολούθηση του ιστορικού ανάπτυξης που μπορεί να υπάρξει.

Από τα διάφορα συστήματα, το www.github.com είναι νομίζω το πιο κατάλληλο για την προσπάθεια αυτή.

[Nisok]

Όντως εξαιρετικό ... !

[Dimitris]

Αυτό το github δεν το ξερα και φαίνεται αρκετά εύχρηστο, ευχαριστώ.

Όπως είπα αυτό είναι απλώς μια αρχή. Ελπίζω αυτό το project μου να ευδοκιμήσει (όχι όπως όλα τα υπόλοιπα )