27ος ΠΔΠ Γ' Φάση: Σουπερμάρκετ (supermarket) - Λύση

Επεξήγηση εκφώνησης

Για να μεγιστοποιήσουμε την συνολική αξία των δωροεπιταγών, πρέπει ουσιαστικά να μεγιστοποιήσουμε το άθροισμα της αξίας των προϊόντων στις θέσεις που είναι πολλαπλάσια του \(K\). Ας πάρουμε το πρώτο παράδειγμα από την εκφώνηση.

5 1 2
10 2 6 4 8

Άρα έχουμε στη διάθεσή μας \(1\) μετακίνηση και τα πολλαπλάσια του \(2\) είναι οι θέσεις των δωροεπιταγών. Στην παρακάτω εικόνα οι θέσεις αυτές παριστάνονται με πράσινο χρώμα.

Αν δεν κάνουμε καμία μετακίνηση η συνολική αξία θα είναι \(2 + 4 = 6\). Αν όμως μετακινήσουμε το πρώτο (ή και το δεύτερο) στοιχείο, τότε αυξάνουμε τη συνολική αξία σε \(6 + 8 = 14\).

Λύση με brute force

Η πιο απλή λύση είναι να δοκιμάσουμε όλους τους πιθανούς τρόπους να μετακινήσουμε \(M\) αντικείμενα. Ξεκινώντας από την αρχή της λίστας και πηγαίνοντας προς το τέλος, κάθε αντικείμενο μπορούμε είτε να το μετακινήσουμε είτε να το αφήσουμε στη θέση του, με μόνο περιορισμό να μην μετακινήσουμε πάνω από \(M\) αντικείμενα συνολικά.

Μπορούμε να κρατάμε ποια αντικείμενα έχουμε μετακινήσει σε ένα πίνακα \(\mathit{moved}[i]\), όπου \(\mathit{moved}[i] = \mathit{false}\) αν δεν μετακινήσαμε το αντικείμενο και \(\mathit{moved}[i] = \mathit{true}\) αν το μετακινήσαμε στο τέλος του ιμάντα. Σε κώδικα μπορούμε να το γράψουμε κάπως έτσι:

void iterate(int pos, int total_moved) {
  // Αφού θέσουμε το moved για όλα τα αντικείμενα μπορούμε να υπολογίσουμε
  // την συνολική αξία των δωροεπιταγών.
  if (pos == N + 1) {
    int score = calculate_total_score(total_moved);
    if (score > best_score) {
      best_score = score;
    }
    return;
  }

  moved[pos] = 0;
  iterate(pos + 1, total_moved);

  if (total_moved == M) return;
  moved[pos] = 1;
  iterate(pos + 1, total_moved + 1);
}

Η συνάρτηση \(\mathit{calculate\_total\_score}\) πρέπει να υπολογίσει την τελική θέση κάθε αντικειμένου και να προσθέσει την αξία του αν η θέση είναι πολλαπλάσιο του \(K\).

Παρατήρηση 1: Έστω ότι έχουμε μετακινήσει \(k\) από τα \(i - 1\) πρώτα αντικείμενα. Τότε αν δεν μετακινήσουμε το \(i\)-οστό αντικείμενο, στην τελική διάταξη θα βρίσκεται στην θέση \(i-k\).

Παρατήρηση 2: Έστω ότι έχουμε μετακινήσει \(k - 1\) από τα \(i - 1\) πρώτα αντικείμενα και συνολικά μετακινήσαμε \(m\). Τότε αν μετακινήσουμε το \(i\)-οστό αντικείμενο, στην τελική διάταξη θα βρίσκεται στην θέση \(N - m + k\).

int calculate_total_score(int total_moved) {
  int current_moved = 0;
  int score = 0;

  for (int i = 1; i <= N; ++i) {
    int final_pos = -1;

    if (moved[i]) {
      current_moved++;
      // Τα k αντικείμενα που μετακινήθηκαν μετά από το i είναι total_moved - current_moved
      // άρα N - k = N - (total_moved - current_moved) = N - total_moved + current_moved.
      final_pos = N - total_moved + current_moved;
    } else {
      final_pos = i - current_moved;
    }

    if (final_pos % K == 0) {
      score += items[i];
    }
  }

  return score;
}

Το μόνο που μας μένει είναι να καλέσουμε την συνάρτηση \(\mathit{iterate(1, 0)}\).

Η πολυπλοκότητα της λύσης είναι \(\mathcal{O}(2^N)\), αφού για κάθε στοιχείο έχουμε δύο επιλογές, είτε να το μετακινήσουμε είτε όχι.

Πιο συγκεκριμένα, η πολυπλοκότητα είναι όσος ο αριθμός των επιλογών που μπορούμε να κάνουμε, που είναι ο αριθμός των τρόπων με τους οποίους μπορούμε να διαλέξουμε \(m\) αντικείμενα από τα \(N\) με \(0 \leq m \leq M\). Αυτό μπορεί να γραφτεί ώς \(\mathit{total\_states}(N, M) = \sum_{m=0}^M{\binom{N}{m}}\). Για \(M = N\), \(\mathit{total\_states}(N, N) = \mathcal{O}(2^N)\), και για τιμές του \(M\) κοντά στο \(N\) δεν έχουν μεγάλη διαφορά οι πολυπλοκότητες, αλλά για μικρές τιμές του \(M\) σε σχέση με το \(N\), η πολυπλοκότητα μπορεί να είναι σημαντικά μικρότερη.

Δείτε ολοκληρωμένη τη λύση εδώ.

Λύση με δυναμικό προγραμματισμό

Παρατήρηση 1: Για να υπολογίσουμε την τελική θέση ενός προϊόντος, όπως είδαμε στην προηγούμενη λύση χρειάζεται να ξέρουμε την αρχική του θέση, πόσα αντικείμενα από αυτά που έχουν προηγηθεί έχουν μετακινηθεί και πόσα αντικείμενα έχουν μετακινηθεί συνολικά (το τελευταίο το χρειαζόμαστε για την θέση των αντικειμένων που έχουν μετακινηθεί).

Παρατήρηση 2: Αν γνωρίζουμε τον συνολικό αριθμό των μετακινήσεων που θα γίνουν, και έχουμε λύσει το πρόβλημα για τα πρώτα \(i\) αντικείμενα (έχοντας ίσως μετακινήσει κάποια απο αυτά), τότε η συνολική λύση είναι ανεξάρτητη από το ποια αντικείμενα έχουν μετακινηθεί, και εξαρτάται μόνο από το πόσα αντικείμενα έχουν μετακινηθεί από τα πρώτα \(i\).

Χρησιμοποιώντας αυτές τις παρατηρήσεις μπορούμε να ορίσουμε την συνάρτηση \(\mathit{dp}(i, \mathit{current\_moves}, \mathit{total\_moves})\), η οποία μας δίνει την βέλτιστη λύση για τα πρώτα \(i\) αντικείμενα αν έχουμε κάνει \(\mathit{current\_moves}\) μετακινήσεις στα πρώτα \(i\) αντικείμενα και συνολικά θα κάνουμε \(\mathit{total\_moves}\) μετακινήσεις.

Το επόμενο βήμα είναι να υπολογίσουμε τις τιμές της συνάρτησης \(\mathit{dp}\). Μπορούμε να πάρουμε την τιμή του \(\mathit{dp}(i, \mathit{current\_moves}, \mathit{total\_moves})\) επαγωγικά. Έχουμε \(2\) επιλογές για το \(i\)-οστό αντικείμενο, είτε το μετακινούμε είτε όχι.

• Αν μετακινήσουμε το \(i\)-οστό αντικείμενο, τότε μέχρι το \(i - 1\) έχουμε μετακινήσει \(\mathit{current\_moves - 1}\) αντικείμενα. Όπως είδαμε στην αρχική λύση, η τελική θέση του αντικειμένου σε αυτή τη περίπτωση είναι \(N - \mathit{total\_moves} + \mathit{current\_moves}\). Άρα τότε έχουμε

• Αν δεν μετακινήσουμε το \(i\)-οστό αντικείμενο, τότε μέχρι το \(i - 1\) έχουμε μετακινήσει \(\mathit{current\_moves}\) αντικείμενα. Όπως είδαμε στην αρχική λύση, η τελική θέση του αντικειμένου σε αυτή τη περίπτωση είναι \(i - \mathit{current\_moves}\). Άρα τότε έχουμε

Καθώς θέλουμε τη βέλτιστη λύση για το \(\mathit{dp}(i, \mathit{current\_moves}, \mathit{total\_moves})\), η τελική τιμή είναι η μέγιστη από τις δύο παραπάνω, εφόσον τηρούνται οι απαραίτητες συνθήκες (\(\mathit{current\_moves} \leq i\) και \(\mathit{current\_moves} \leq \mathit{total\_moves} \leq N\)).

Η τελική βέλτιστη λύση είναι η μέγιστη από τα \(\mathit{dp}(N, \mathit{total\_moves}, \mathit{total\_moves})\) για κάθε \(\mathit{total\_moves} = 0, \ldots, M\).

Καθώς το \(\mathit{total\_moves}\) μένει σταθερό, κατά την επαγωγή μπορούμε να απλοποιήσουμε την συνάρτηση σε \(\mathit{dp}(i, \mathit{current\_moves})\) και να την υπολογίσουμε για κάθε τιμή του \(\mathit{total\_moves}\). Επίσης μπορούμε να αποθηκεύουμε τις τιμές της συνάρτησης σε έναν πίνακα dp[i][current_moves] με διαστάσεις \(N \times M\).

   // Αρχικοποιούμε τον πίνακα dp
   dp[0][0] = 0;

   // Ελέγχουμε όλα τα πιθανά πλήθη συνολικών μετακινήσεων
   int best_score = 0;
   for (int moves = 0; moves <= M; ++moves)
   {
      for (int i = 1; i <= N; ++i)
      {
         for (int curr_moves = 0; curr_moves <= moves; ++curr_moves)
         {
            // Δεν μπορούμε να μετακινήσουμε πιο πολλά αντικείμενα από αυτά που
            // έχουμε συναντήσει.
            if (curr_moves > i)
               break;

            dp[i][curr_moves] = 0;

            // Περίπτωση που δεν μετακινούμε το i-οστό αντικείμενο.
            if (curr_moves <= i - 1)
               dp[i][curr_moves] = dp[i - 1][curr_moves] + items[i] * is_coupon_position(i - curr_moves);

            // Περίπτωση που μετακινούμε το i-οστό αντικείμενο.
            if (curr_moves > 0)
            {
               int new_score = dp[i - 1][curr_moves - 1] + items[i] * is_coupon_position(N - moves + curr_moves);
               if (dp[i][curr_moves] < new_score)
                  dp[i][curr_moves] = new_score;
            }
         }
      }
      if (best_score < dp[N][moves])
         best_score = dp[N][moves];
   }

Κάθε υπολογισμός του πίνακα dp θέλει \(\mathcal{O}(N \cdot M)\) χρόνο. Αφού έχουμε \(\mathcal{O}(M)\) επαναλήψεις, η συνολική πολυπλοκοτητα του αλγορίθμου είναι \(\mathcal{O}(N \cdot M^2)\).

Δείτε ολόκληρη τη λύση εδώ.

Παρατηρώντας ότι σε κάθε επανάληψη του \(i\) χρησιμοποιούμε μόνο τιμές της μορφής \(\mathit{dp}[i-1][\cdot]\), μπορούμε να μειώσουμε την μνήμη σε \(\mathcal{O}(M)\) (δείτε τον κώδικα εδώ).