L15 · Δυναμικός Προγραμματισμός II — Σακίδιο & Μέγιστη Κοινή Υπακολουθία

Τι θα δούμε

Δύο κλασικά DP προβλήματα — και ένα νέο δίδαγμα. Στο L14 τα υποπροβλήματα παραμετροποιήθηκαν με μία μεταβλητή ($j$ = «τα πρώτα $j$ αιτήματα»). Εδώ θα δούμε ότι αυτό δεν αρκεί πάντα: το πρόβλημα του σακιδίου χρειάζεται δύο μεταβλητές. Μετά, η μέγιστη κοινή υπακολουθία δείχνει DP πάνω σε δύο συμβολοσειρές.

Το πρόβλημα του σακιδίου (knapsack)

Διατύπωση

Είσοδος: $n$ αντικείμενα και ένα «σακίδιο». Το αντικείμενο $i$ έχει βάρος $w_i>0$ και αξία $v_i>0$. Το σακίδιο αντέχει το πολύ $W$ κιλά.

Στόχος: διάλεξε υποσύνολο αντικειμένων που χωράει ($\sum w_i\le W$) και μεγιστοποιεί τη συνολική αξία.

Ο άπληστος δεν αρκεί

Ο λόγος $v_i/w_i$ απαντά στο «πόσο καλό είναι ένα αντικείμενο μόνο του». Αγνοεί όμως ότι το σακίδιο έχει πεπερασμένο χώρο και ότι ο στόχος είναι ο καλύτερος συνδυασμός. Ο άπληστος γεμίζει το σακίδιο με μικρά αντικείμενα καλού λόγου και μετά κολλάει με ένα κενό που κανένα μεγαλύτερο αντικείμενο δεν χωράει να καλύψει. Δες το να συμβαίνει βήμα-βήμα:

Πρώτη απόπειρα — και γιατί αποτυγχάνει

Στο L14 κάθε DP πρόβλημα λύθηκε με μία παράμετρο. Ας δοκιμάσουμε το ίδιο: ορίζουμε $\text{OPT}(i)$ = η μέγιστη αξία που πετυχαίνουμε χρησιμοποιώντας μόνο τα αντικείμενα $1,\dots ,i$. Όπως πάντα, κοιτάμε το τελευταίο αντικείμενο $i$ — μέσα ή έξω;

• Το $i$ ΕΞΩ: μένει το ίδιο πρόβλημα με ένα αντικείμενο λιγότερο → $\text{OPT}(i-1)$.
• Το $i$ ΜΕΣΑ: κερδίζουμε αξία $v_i$… αλλά το $i$ καταναλώνει $w_i$ κιλά χώρου. Και εδώ η αναδρομή κολλάει: για να πούμε αν το $i$ χωράει καν, πρέπει να ξέρουμε πόσος χώρος έχει ήδη ξοδευτεί — κι αυτό η $\text{OPT}(i-1)$ δεν μας το λέει.

Το πρόβλημα είναι βαθύτερο από «μια λεπτομέρεια που λείπει». Σκέψου τι σημαίνει ένας αριθμός $\text{OPT}(i)$: «η καλύτερη αξία με τα πρώτα $i$ αντικείμενα». Όμως το καλύτερο prefix για το μέλλον δεν είναι αυτό με τη μεγαλύτερη αξία τώρα — είναι αυτό που αφήνει αρκετό χώρο για ό,τι ακολουθεί. Δύο διαφορετικές επιλογές στα ίδια $i$ αντικείμενα μπορεί να έχουν διαφορετική αξία και διαφορετικό ελεύθερο χώρο· ένας μόνο αριθμός δεν χωράει να κρατήσει και τα δύο. Παίξε με τις δύο στήλες:

Η σωστή αναδρομή — δύο μεταβλητές

Σκεφτόμαστε ξανά το αντικείμενο $i$:

• Το $i$ ΕΞΩ: η καλύτερη λύση από τα $1,\dots ,i-1$ με την ίδια χωρητικότητα → $\text{OPT}(i-1,w)$.
• Το $i$ ΜΕΣΑ (μόνο αν $w_i\le w$): «ξοδεύουμε» $w_i$ χώρο και κερδίζουμε $v_i$ αξία, και λύνουμε το υπόλοιπο με χωρητικότητα $w-w_i$ → $v_i+\text{OPT}(i-1,w-w_i)$.

Ο αλγόριθμος

Δες τον πίνακα να γεμίζει γραμμή-γραμμή. Σε κάθε γραμμή φωτίζεται το κελί $M[i][W]$ και τα δύο κελιά της προηγούμενης γραμμής από τα οποία εξαρτάται:

Πολυπλοκότητα — μια λεπτή παγίδα

Ο αλγόριθμος γεμίζει έναν πίνακα $n\times W$, ένα κελί τη φορά, άρα τρέχει σε $\Theta (n\cdot W)$. Δεν έχει εκθέτες, δεν έχει $2^n$ — μοιάζει πολυωνυμικός. Δεν είναι.

Το $W$ δεν είναι «πλήθος αντικειμένων»· είναι ένας αριθμός που δίνεται στην είσοδο. Κι έναν αριθμό τιμής $W$ τον γράφεις με μόλις ${\log }_{2}W$ δυφία. Άρα το πραγματικό μέγεθος της εισόδου μεγαλώνει σαν $\log W$, ενώ ο χρόνος μεγαλώνει σαν $W$ — δηλαδή σαν $2^{(\text{δυφιˊα})}$. Αυτό είναι εκθετικό ως προς το μέγεθος της εισόδου. Δοκίμασε να διπλασιάσεις το $W$ και μέτρα:

Μέγιστη κοινή υπακολουθία (LCS)

Διατύπωση

Είσοδος: δύο συμβολοσειρές $x=x_1{x}_2\cdots x_m$ και $y=y_1{y}_2\cdots y_n$.

Στόχος: το μέγιστο μήκος μιας ακολουθίας $z_1{z}_2\cdots z_k$ που είναι ταυτόχρονα υπακολουθία και των δύο.

Η διάκριση είναι λεπτή κι αξίζει να την «πιάσεις» πριν προχωρήσουμε — πάτησε γράμματα και δες:

Η αναδρομή

Ίδιο μοτίβο με το L14 — αλλά τώρα έχουμε δύο ακολουθίες, άρα φυσικά δύο παραμέτρους. Ορίζουμε $\text{OPT}(i,j)$ = το μέγιστο μήκος κοινής υπακολουθίας των προθεμάτων $x_1\cdots x_i$ και $y_1\cdots y_j$. Για να σπάσουμε το πρόβλημα, κοιτάμε τους τελευταίους χαρακτήρες, $x_i$ και $y_j$:

• $x_i=y_j$. Έχουμε δύο ίδια γράμματα στις δύο άκρες — κι ένα ζευγάρι ίδιων γραμμάτων είναι «δωρεάν» μήκος για την κοινή υπακολουθία. Δεν χάνεις ποτέ τίποτα αν τα ζευγαρώσεις: υπάρχει πάντα μια βέλτιστη λύση που τα χρησιμοποιεί ως τελευταίο της στοιχείο. Άρα κερδίζουμε $1$, και μένει η LCS των $x_1\cdots x_{i-1}$ και $y_1\cdots y_{j-1}$ → $1+\text{OPT}(i-1,j-1)$.
• $x_i\ne y_j$. Δύο διαφορετικά γράμματα δεν γίνεται να είναι και τα δύο το τελευταίο στοιχείο μιας κοινής υπακολουθίας — άρα τουλάχιστον το ένα δεν χρησιμοποιείται. Πετάμε είτε το $x_i$ (μένει LCS των $x_1\cdots x_{i-1}$ και $y_1\cdots y_j$) είτε το $y_j$ (μένει LCS των $x_1\cdots x_i$ και $y_1\cdots y_{j-1}$). Δεν ξέρουμε ποιο — τα δοκιμάζουμε και τα δύο και κρατάμε το $\max$.

Ο αλγόριθμος

Παράδειγμα. Δες τον πίνακα να γεμίζει γραμμή-γραμμή για $x=\text{ABCB}$ και $y=\text{BDCAB}$, και μετά το πέρασμα προς τα πίσω να ανακτά την ίδια την υπακολουθία:

Ο πίνακας έχει $(m+1)(n+1)$ κελιά, κάθε ένα υπολογίζεται σε $O(1)$ → πολυπλοκότητα $\Theta (mn)$. Το κάτω-δεξιά κελί $M[m,n]$ δίνει το μήκος· το πέρασμα προς τα πίσω από εκεί δίνει μια συγκεκριμένη μέγιστη κοινή υπακολουθία (εδώ, το BCB).

Κλείδωσε τη γνώση

Βάλε στη σειρά τα βήματα του DP για το σακίδιο:

Και συμπλήρωσε τα κενά:

Μοτίβο σκέψης