Αλγόριθμοι και Πολυπλοκότητα, 2η Σειρά Ασκήσεων

Αγιάννης Κωνσταντίνος 03116352

Άσκηση 1

Τα ζεύγη είναι στη μορφή (βάρος,αντοχή)

1

Αντιπαράδειγμα

η διάταξη (100,1), (2,200) αποτυγχάνει

ενώ η διάταξη

(2,200), (100,1) είναι σωστή

2

Αντιπαράδειγμα

η διάταξη (1,5), (100,4) αποτυγχάνει

ενώ η διάταξη

(100,4), (1,5) είναι σωστή

3

Έστω ότι υπάρχει η λύση \(((w_n,d_n),..,(w_1,d_1))\)

Θα δείξουμε ότι και η παραπάνω στοίβαξη με βάση το w+d αποτελεί λύση.

Θα χρησιμοποιήσουμε επαγωγή.

Για n = 1 προφανώς ισχύει.

Έστω ότι ισχύει για τo n = k. Θα αποδείξουμε ότι ισχύει για το k+1.

Παίρνουμε το k+1 και το βάζουμε στή θέση j στην οποία παραμένουν τα στοιχεία ταξινομημένα.

(β)

Αρχικά ταξινομούμε σε φθίνουσα σειρά ως προς w+d. Ξέρουμε ότι στην τελική στοίβα μπορούμε να τα έχουμε σε φθίνουσα σειρά ως προς w+d.

Το state είναι dp(n,d) η μέγιστη αξία αντικειμένων περιλαμβάνοντας μόνο από τα n πρώτα και έχοντας αντοχή για τα επόμενα που θα μπουν από πάνω τουλάχιστον d.

Η αναδρομική σχέση γίνεται λοιπόν

dp(n,d) =

Στην πρώτη περίπτωση παίρνουμε στη δεύτερη δεν παίρνουμε το n-οστό

όπου p(n) η αξία, w(n) το βάρος και d(n) η αντοχή του n-οστού κουτιού.

Η πολυποκότητα του αλγορίθμου είναι \(O(n^2d)\)

Άσκηση 2

Το πρόβλημα είναι σχεδόν το αυτό του κλέφτη με τη σάκα (kanpsack). To state μας είναι dp[c][i] η μέγιστη αξία αντικειμένων με αξία έως c, για τις πρώτες i χώρες. Τότε η αναδρομική σχέση είναι:

dp[c][i] =

\[ -\infty, c < 0 \] \[ 0, i < 0 \] \[ max_{j=0..k_j-1}(dp\left[ c-c_j\right] \left[ i-1 \right] ), otherwise \]

H πολυπλοκότητα του αλγορίθμου είναι \(O\left(c\left( \sum_{i=0}^{i=n-1}k_j\right)\right)\).

Για την εύρεση της συλλογής, πηγαίνουμε προς τα πίσω και εκτυπώνουμε τα αναμνηστικά που δημηουργούν το αντίστοιχο αποτέλεσμα. Αν θέλουμε να κάνουμε τη ζωή μας πιο εύκολη, απλά στο state βάζουμε ένα δείκτη προς τα πίσω δείχνοντας από ποια κατάσταση ήρθαμε, και ακολουθούμε τους δείχτες ανάποδα.

Άσκηση 3

Φτιάχνουμε ζεύγη (q,t,x) όπου q η αξία, t ο τύπος και x η θέση του κουτιού, για κάθε κουτί και τα ταξινομούμε ως προς q. Το state μας είναι dp[n][q] η ελάχιστη απόσταση που πρέπει να διανύσουμε έχοντας φάει q σοκολατάκια και βρισκόμενοι στη θέση n του ταξινομημένου πίνακα. Η αναδρομική σχέση γίνεται:

dp(n,q) = \[ \infty, q<0 \] \[ 0, i = 0 \] \[ min_{i=1..n}(t_n \neq t_i ? dp(i,q-q_n) + |x_n - x_i|: \infty) \]

Η πολυπλοκότητα του αλγορίθμου είναι \(Ο(n^2Q)\)

Για να βρούμε ποια κουτιά ανοίξαμε, τρέχουμε τον αλγόριθμο ανάποδα και βλέπουμε κάθε φορά πιο κουτί επιλέξαμε. Αν θέλουμε να κάνουμε τη ζωή μας πιο εύκολη, απλά στο state βάζουμε ένα δείκτη προς τα πίσω δείχνοντας από ποια κατάσταση ήρθαμε, και ακολουθούμε τους δείχτες ανάποδα.

Άσκηση 5

(α)

(β)

Για να βρούμε αν είναι δυνατή μία τέτοια λύση: Ξεκινάμε από τη ρίζα, την επιλέγουμε. και κάνοντας BFS προς τα παιδιά επιλέγουμε τους κάμβους ανά βάθος z. Αν οι κόμβοι που χρησιμοποιήσαμε είναι το πολύ Κ επιστρέφουμε ΝΑΙ, αλλιώς ΟΧΙ. Η πολυπλοκότητα του αλγορίθμου είναι \(O(n)\).

Για να λύσουμε τοα αρχικό πρόβλημα, απλά κάνουμε διαδική αναζήτηση στο z. Η πολυπλοκότητα τότε γίνεται \(O(nlogn)\)