Πρόγραμμα για το πρόβλημα Bridge and Torch


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Απολύτως eBay Quora Snapdeal Τερατάτα Times Internet
Παράταξη Δυναμικός προγραμματισμός

Δήλωση προβλήματος

Το πρόβλημα "Bridge and Torch" δηλώνει ότι σας δίνεται μια σειρά χρόνου που χρειάζεται ένα άτομο να διασχίσει τη γέφυρα. Δεδομένου ότι είναι ώρα, περιλαμβάνει θετικούς ακέραιους αριθμούς. Μαζί με το χρόνο μας δίνεται μια γέφυρα, την οποία ένα άτομο πρέπει να διασχίσει. Η γέφυρα επιτρέπει στη διέλευση μόνο δύο ατόμων κάθε φορά. Μεταφέρουν έναν φακό ενώ διασχίζουν. Και αφού υπάρχει ένας και μοναδικός φακός. Ένα από τα άτομα από την άλλη πλευρά θα πρέπει να επιστρέψει και να επιστρέψει το φακό στην αρχική πλευρά. Όταν δύο άτομα διασχίζουν τη γέφυρα, μπορούν να διασχίσουν την ταχύτητα ενός πιο αργού ατόμου. Βρείτε τον ελάχιστο συνολικό χρόνο κατά τον οποίο όλα τα άτομα μπορούν να διασχίσουν τη γέφυρα.

Παράδειγμα

Πρόγραμμα για το πρόβλημα Bridge and Torch

timeToCross = {1, 2, 3}
6

Επεξήγηση: Πρώτα, τα άτομα 1 και 2 διασχίζουν τη γέφυρα. Έτσι, μέχρι τώρα έχουν περάσει 2 δευτερόλεπτα. Τώρα το άτομο 1 διασχίζει ή επιστρέφει στην αρχική πλευρά. Στη συνέχεια, τα άτομα 2 και 3 διασχίζουν τη γέφυρα. Έτσι, ο συνολικός χρόνος που απαιτείται είναι = 2 + 1 + 3 = 6.

Προσέγγιση για το πρόβλημα της γέφυρας και του φακού

Naive προσέγγιση

Μπορούμε να χρησιμοποιήσουμε την αναδρομή για να γράψουμε ένα πρόγραμμα για πρόβλημα γέφυρας και φακού, για να βρούμε όλα τα μετάθεσητου χρόνου να διασταυρώσετε τη σειρά. Στη συνέχεια, πρώτα μετακινούμε δύο άτομα από τη μία πλευρά στην άλλη με τον φακό. Στη συνέχεια, το γρηγορότερο άτομο από άλλη πλευρά (προορισμός) επιστρέφει στην αρχική πλευρά. Κάνοντας αυτό, μπορούμε να βρούμε τον ελάχιστο χρόνο που απαιτείται για την αποστολή όλων των ατόμων από τη μία πλευρά στην άλλη ικανοποιώντας όλες τις προϋποθέσεις.

Αλλά αυτός ο αλγόριθμος απαιτεί εκθετικό χρόνο για να εκτελεστεί. Επομένως απαιτείται μια αποτελεσματική προσέγγιση.

Αποτελεσματική προσέγγιση

Μπορούμε να γράψουμε ένα πρόγραμμα για πρόβλημα γέφυρας και φακού χρησιμοποιώντας μια αποτελεσματική προσέγγιση που θα χρησιμοποιεί δυναμικό προγραμματισμό αφού μπορούμε να διαιρέσουμε το αρχικό πρόβλημα σε μικρότερα υποπροβλήματα τα οποία μπορούν να υποδιαιρεθούν περαιτέρω σε μικρότερα υποπροβλήματα. Έτσι, αντί να υπολογίζετε ή να επιλύετε τα μικρότερα υποπροβλήματα πολλές φορές. Θα αποθηκεύσουμε το αποτέλεσμα και μετά θα συνδυάσουμε αυτά τα αποτελέσματα για να βρούμε την απάντησή μας. 

Υπάρχουν ορισμένα πράγματα που πρέπει να σημειωθούν κατά την επίλυση αυτού του προβλήματος. Όταν δύο άτομα διασχίζουν τη γέφυρα, χρησιμοποιείται η ταχύτητα του πιο αργού ατόμου. Ο φακός πρέπει να επιστρέψει στην αρχική πλευρά. Τώρα, πρέπει να εκπροσωπήσουμε τα άτομα στην αριστερή και τη δεξιά πλευρά. Μπορούμε επίσης να πούμε τα άτομα στην αρχική πλευρά και την πλευρά προορισμού. 

Θα το χρησιμοποιησουμε bitmask για να αντιπροσωπεύσετε μια από τις πλευρές και την άλλη πλευρά μπορεί εύκολα να βρεθεί χρησιμοποιώντας κάποιους χειρισμούς bit. Λαμβάνοντας υπόψη ότι έχουμε τρία άτομα, χρησιμοποιούμε ένα bitmask μεγέθους «3» για να αντιπροσωπεύσουμε 3 άτομα. Εάν ένα άτομο (2ο) βρίσκεται στην πλευρά προορισμού. Το bitmask που αντιπροσωπεύει την αρχική πλευρά θα είναι 101, το bitmask για την πλευρά προορισμού = (1 < XOR(bitmask που αντιπροσωπεύει την αρχική πλευρά). Έτσι (2 ^ n-1) XOR (5) = 7 XOR 5 = 2.

Τώρα, θα χρησιμοποιήσουμε 2-διαστατική Δυναμικός προγραμματισμός dp [μάσκα] [κατεύθυνση κίνησης], όπου η μάσκα αντιπροσωπεύει τον ελάχιστο χρόνο που απαιτείται για να μετακινήσετε το άτομο που αντιπροσωπεύει τη μάσκα από αριστερά προς τα δεξιά (κατεύθυνση κίνησης = 0) ή δεξιά προς αριστερά (κατεύθυνση κίνησης = 1),

Κώδικας

Κωδικός C ++ για το πρόβλημα Bridge and Torch

#include <bits/stdc++.h>
using namespace std;

int solveBridgeAndTorchProblem(int mask, bool direction, vector<int> &timeToCross, vector<vector<int>> &dp)
{
    int n = timeToCross.size();
    // if nobody is left to transfer
  if (!mask)
    return 0;
    if(dp[mask][direction]!=-1)
        return dp[mask][direction];

  int transferredMask = ((1<<n)-1)^mask;
    int res = 0;
  // transfer people from left to right (from destination to start)
  if (direction == 1) {
    int minRow = INT_MAX, person;
    for (int i = 0; i < n; ++i) {
            // choose the person with smallest time to cross bridge
      if (transferredMask & (1 << i)) {
        if (minRow > timeToCross[i]) {
          person = i;
          minRow = timeToCross[i];
        }
      }
    }

    // now send this person to let and solve for smaller problem
    res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
  }
  else {

    // __builtin_popcount() counts the bits in mask
    if (__builtin_popcount(mask) == 1) {
      for (int i=0;i<n;++i) {
        // since there is only a single person on starting side, return him
        if (mask&(1<<i)) {
          res = timeToCross[i];
          break;
        }
      }
    }
    else {

      // find the minimum time by solving for each pair
      res = INT_MAX;
      for(int i=0;i<n;++i) {
                // if ith person is not on right side, then do nothing
        if(!(mask&(1<<i)))
          continue;
                // else find another person and try to cross the bridge
        for(int j=i+1;j<n;++j) {
          if(mask&(1<<j)){
            // time to cross the bridge for current pair
            int val = max(timeToCross[i], timeToCross[j]);
            // solve for smaller subproblems
            val += solveBridgeAndTorchProblem(mask^(1<<i)^(1<<j), direction^1,timeToCross,dp);
            // update the answer
            res = min(res, val);
          }
        }
      }
    }
  }
  return dp[mask][direction] = res;
}

int main()
{
  int n;cin>>n;
  vector<int> timeToCross(n);
  for(int i=0;i<n;i++)cin>>timeToCross[i];
  vector<vector<int>> dp(1<<20, vector<int>(2,-1));
  int mask = (1<<n)-1;
  cout << solveBridgeAndTorchProblem(mask, 0, timeToCross, dp);
  return 0;
}
5
25 6 5 8 4
54

Κωδικός Java για το πρόβλημα Bridge και Torch

import java.util.*;

class Main{

    static int countBits(int n){
        int nn = n;
        int cnt = 0;
        while(n>0){
            if((n&1) == 1)
                cnt++;
            n = n/2;
        }
        n = nn;
        return cnt;
    }

    static int solveBridgeAndTorchProblem(int mask, int direction, int timeToCross[], int dp[][])
    {
        int n = timeToCross.length;
        // if nobody is left to transfer
        if (mask==0)
            return 0;
        if(dp[mask][direction]!=-1)
            return dp[mask][direction];

        int transferredMask = ((1<<n)-1)^mask;
        int res = 0;
        // transfer people from left to right (from destination to start)
        if(direction == 1) {
            int minRow = Integer.MAX_VALUE, person=0;
            for(int i = 0; i < n; ++i) {
                // choose the person with smallest time to cross bridge
                if((transferredMask & (1 << i)) > 0) {
                    if (minRow > timeToCross[i]) {
                        person = i;
                        minRow = timeToCross[i];
                    }
                }
            }

            // now send this person to let and solve for smaller problem
            res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
        }
        else {

            // countBits() counts the bits in mask
            if (countBits(mask) == 1) {
                for (int i=0;i<n;++i) {
                    // since there is only a single person on starting side, return him
                    if((mask&(1<<i))!=0) {
                        res = timeToCross[i];
                        break;
                    }
                }
            }
            else {

                // find the minimum time by solving for each pair
                res = Integer.MAX_VALUE;
                for(int i=0;i<n;++i) {
                    // if ith person is not on right side, then do nothing
                    if((mask&(1<<i))== 0)
                        continue;
                    // else find another person and try to cross the bridge
                    for(int j=i+1;j<n;++j) {
                        if((mask&(1<<j))>0){
                            // time to cross the bridge for current pair
                            int val = Math.max(timeToCross[i], timeToCross[j]);
                            // solve for smaller subproblems
                            val += solveBridgeAndTorchProblem(mask^(1<<i)^(1<<j), direction^1,timeToCross,dp);
                            // update the answer
                            res = Math.min(res, val);
                        }
                    }
                }
            }
        }
        return dp[mask][direction] = res;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] timeToCross = new int[n];
        for(int i=0;i<n;i++)
            timeToCross[i] = sc.nextInt();
        int dp[][] = new int[1<<20][2];
        for(int i=0;i<(1<<20);i++){
            dp[i][0] = -1;
            dp[i][1] = -1;
        }
        int mask = (1<<n)-1;
        int answer = solveBridgeAndTorchProblem(mask, 0, timeToCross, dp);
        System.out.println(answer);
    }

}
5 
25 6 5 8 4
54

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας: O (2 ^ N * N ^ 2)

Χρησιμοποιούμε bitmask για την αναπαράσταση αριθμών Ν, που συμβάλλει στο 2 ^ n. Και έπειτα ελέγχουμε για κάθε ζεύγος χρησιμοποιώντας δύο ένθετους βρόχους που μας δίνουν έναν παράγοντα N ^ 2. Έτσι, η πολυπλοκότητα του χρόνου είναι O (2 ^ N * N ^ 2).

Διαστημική πολυπλοκότητα: Ο (2 ^ Ν)

Χρησιμοποιούμε Dp μέσω bitmask εδώ. Και δεδομένου ότι ο πίνακας DP εξαρτάται από την κατεύθυνση και το bitmask, όπου υπάρχουν μόνο 2 κατευθύνσεις. Έχουμε εκθετική πολυπλοκότητα χώρου O (2 ^ N).