Η τσάντα του ή το σακίδιο (knapsack) μπορεί να μεταφέρει συνολικό βάρος μέχρι W κιλά. Υπάρχουν δύο είδη από τα οποία μπορεί να επιλέξει με βαρύ w1 ....wn χρηματική αξία v1 ....vn . Ποιος είναι ο πλέον πολύτιμος συνδυασμός που μπορεί να τοποθετήσει τα είδη στην τσάντα του;
Για παράδειγμα, έστω W=10
Είδος Βάρος Τιμή
1 6 30€
2 3 14€
3 4 16€
4 2 9€
Υπάρχουν δύο εκδοχές αυτού του προβλήματος. Αν υπάρχουν διαθέσιμες απεριόριστες ποσότητες από κάθε είδος, η βέλτιστη λύση είναι να διαλέξουμε το είδος 1 και δύο τεμάχια από το είδος 4.
Από την άλλη πλευρά, αν υπάρχει μόνο ένα στοιχείο από κάθε είδος, για παράδειγμα ο κλέφτης έχει διαρρήξει μία γκαλερί τέχνης, το βέλτιστο σακίδιο περιέχει τα είδη 1 και 3.
Όπως και να έχει, καμία εκδοχή αυτού του προβλήματος δεν είναι πιθανό να έχει αλγόριθμο πολυωνυμικού χρόνου. Ωστόσο με τη χρήση δυναμικού προγραμματισμού μπορούν και οι δύο να λυθούν σε χρόνο Ο(nW) που είναι εύλογος όταν το W είναι μικρό, αλλά δεν είναι πολυωνυμικός αφού το μέγεθος της εισόδου είναι ανάλογο του logW αντί τουW.
Αν αυτή η εφαρμογή σας φέρεται κάπως απλοϊκή αντικαταστήστε το "βάρος" με το "χρόνο CPU" και τη φράση "μπορεί να μεταφέρει μόνο W κιλά" με τη φράση "υπάρχουν διαθέσιμες μόνο W χρονικές μονάδες της CPU". Το πρόβλημα του σακιδίου γενικεύει μία μεγάλη ποικιλία εργασιών επιλογής πόρων με περιορισμούς.
Δημοσίευση σχολίου