Bridge and Torch проблемасы боюнча программа


Кыйынчылык деңгээли катуу
Көп суралган Accolite Окшош Quora Snapdeal Терадата Times Internet
согуштук тизме Динамикалык программалоо

Маселени билдирүү

"Көпүрө жана Факел" көйгөйү боюнча, адам көпүрөдөн өтүшү үчүн бир топ убакыт берилет. Убакыт келгендиктен, ал оң сандардан турат. Убакыт менен кошо бизге адам өтүшү керек болгон көпүрө берилет. Көпүрө бир эле учурда эки кишиден гана өтүүгө мүмкүнчүлүк берет. Алар өтүп бара жатканда факелди көтөрүп турушат. Бир эле факел бар болгондуктан. Экинчи тараптагы адамдардын бири кайтып келип, факелди баштапкы тарабына алып барышы керек. Эки адам көпүрөдөн өткөндө, жайыраак адамдын ылдамдыгы менен өтө алышат. Бардык адамдар көпүрөдөн өтө турган минималдуу жалпы убакытты табыңыз.

мисал

Bridge and Torch проблемасы боюнча программа

timeToCross = {1, 2, 3}
6

Түшүндүрмө: Алгач, 1 жана 2-адамдар көпүрөдөн өтүшөт. Ошентип, ушул убакка чейин 2 секунд өттү. Эми 1 адам өтүп же баштапкы тарабына кайтып келет. Андан кийин 2 жана 3 адам көпүрөдөн өтүшөт. Ошентип, алынган жалпы убакыт = 2 + 1 + 3 = 6.

Көпүрө жана факел көйгөйүнө карата мамиле

Naive Appocach

Биз рекурсияны колдонуп, көпүрө жана факел көйгөйү боюнча программа жазып, бардыгын таба алабыз орун алмаштыруумассивден өтүү убактысы. Андан кийин факел менен эки адамды бир тараптан экинчи жагына жылдырабыз. Андан кийин башка (көздөгөн) тараптан эң ылдам адам баштапкы тарапка кайтып келет. Муну менен, биз бардык шарттарды канааттандырган бир тараптан экинчи тарапка бардык адамдарды жөнөтүү үчүн талап кылынган минималдуу убакытты таба алабыз.

Бирок бул алгоритм иштетүү үчүн экспоненциалдуу убакытты талап кылат. Ошентип натыйжалуу мамиле талап кылынат.

Натыйжалуу мамиле

Көпүрө жана факел көйгөйү боюнча программа жаза алабыз, натыйжалуу ыкманы колдонуп динамикалык программалоо анткени биз баштапкы маселени кичине чакан чакан проблемаларга бөлсө болот, аларды чакан субпроблемаларга бөлсөк болот. Ошентип, чакан чакан проблемаларды бир нече жолу эсептөөнүн же чечүүнүн ордуна. Натыйжаны сактайбыз, андан кийин жоопторду табыш үчүн, ошол натыйжаларды бириктиребиз. 

Бул көйгөйдү чечүүдө көңүл бура турган нерселер бар. Эки адам көпүрөдөн өткөндө, жайыраак адамдын ылдамдыгы колдонулат. Факелди баштапкы тарабына кайтаруу керек. Эми биз сол жактагы жана оң жактагы адамдарды көрсөтүшүбүз керек. Ошондой эле баштапкы жана көздөгөн тараптагы адамдарды айта алабыз. 

Биз колдонобуз битмаска бир тарабын көрсөтүү үчүн, экинчи тарабын бир аз манипуляцияларды колдонуу менен оңой табууга болот. Үч адамыбыз бар экендигин эске алып, биз 3 кишини көрсөтүү үчүн '3' өлчөмүндөгү битмасканы колдонобуз. Эгер бир адам (2-чи) көздөгөн тарапта болсо. Баштапкы тарапты чагылдырган битмаска 101 болот, көздөгөн тараптын битмаскы = (1 < XOR(баштапкы жагын билдирген битмаска). Ошентип (2 ^ n-1) XOR (5) = 7 XOR 5 = 2.

Эми, биз колдонобуз 2-өлчөмдүү Динамикалык программалоо dp [маска] [кыймыл багыты], анда маска масканы чагылдырган адамды солдон оңго (кыймыл багыты = 0) же оңдон солго (кыймыл багыты = 1) жылдыруу үчүн минималдуу убакытты билдирет,

коду

Bridge and Torch Problem үчүн C ++ коду

#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

Bridge and Torch Problem үчүн Java коду

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)

N сандарын көрсөтүү үчүн битмасканы колдонуп жатабыз, бул 2 ^ nге өбөлгө түзөт. Андан кийин, биз N ^ 2 коэффициентин берген эки уяны колдонуп, ар бир түгөйдү текшеребиз. Ошентип, убакыттын татаалдыгы O (2 ^ N * N ^ 2).

Космостун татаалдыгы: O (2 ^ N)

Бул жерде Dp битмаска аркылуу колдонуп жатабыз. Биздин DP массивибиз багытка жана битмаскага көз каранды болгондуктан, 2 гана багыт бар. Бизде O (2 ^ N) экспоненциалдуу мейкиндик татаалдыгы бар.