브리지 및 토치 문제에 대한 프로그램

난이도 하드
자주 묻는 질문 수행자 이베이 Quora 스냅 딜 테라 데이타 타임즈 인터넷
배열 동적 프로그래밍조회수 27

문제 정책

“Bridge and Torch”문제는 사람이 다리를 건너는 데 필요한 일련의 시간이 주어진다고 말합니다. 시간이기 때문에 양의 정수로 구성됩니다. 시간과 함께 우리는 사람이 건너야하는 다리를받습니다. 다리는 한 번에 두 사람 만 건널 수 있습니다. 그들은 건널 때 횃불을 들고 다닙니다. 그리고 하나의 횃불이 있기 때문에. 다른 쪽에서 온 사람 중 한 명이 돌아와서 횃불을 시작쪽으로 가져 가야합니다. 두 사람이 다리를 건너면 느린 사람의 속도로 건널 수 있습니다. 모든 사람이 다리를 건널 수있는 최소 총 시간을 찾으십시오.

브리지 및 토치 문제에 대한 프로그램

timeToCross = {1, 2, 3}
6

설명 : 먼저 사람 1과 2가 다리를 건넜습니다. 그래서 지금까지 2 초가 지났습니다. 이제 사람 1이 교차하거나 시작쪽으로 돌아갑니다. 그런 다음 사람 2와 3이 다리를 건너십시오. 따라서 총 소요 시간은 = 2 + 1 + 3 = 6입니다.

브리지 및 토치 문제에 대한 접근 방식

순진한 접근

재귀를 사용하여 브리지 및 토치 문제에 대한 프로그램을 작성하고 순열교차 배열 시간의 s. 그런 다음 먼저 토치를 사용하여 두 사람을 한 쪽에서 다른쪽으로 이동합니다. 그런 다음 다른 (목적지) 쪽에서 가장 빠른 사람이 처음으로 돌아갑니다. 이렇게하면 모든 조건을 충족하는 모든 사람을 한쪽에서 다른쪽으로 보내는 데 필요한 최소 시간을 찾을 수 있습니다.

그러나이 알고리즘을 실행하려면 기하 급수적 인 시간이 필요합니다. 따라서 효율적인 접근이 필요합니다.

효율적인 접근

효율적인 접근 방식을 사용하여 브리지 및 토치 문제에 대한 프로그램을 작성할 수 있습니다. 동적 프로그래밍 초기 문제를 더 작은 하위 문제로 나눌 수 있기 때문에 더 작은 하위 문제로 더 세분화 할 수 있습니다. 따라서 작은 하위 문제를 여러 번 계산하거나 해결하는 대신. 결과를 저장하고 그 결과를 결합하여 답을 찾습니다. 

이 문제를 해결하는 동안 몇 가지 유의해야 할 사항이 있습니다. 두 사람이 다리를 건널 때 느린 사람의 속도가 사용됩니다. 토치는 처음으로 되돌려 야합니다. 이제 우리는 왼쪽과 오른쪽에있는 사람을 표현해야합니다. 우리는 또한 초기 측과 목적지 측에있는 사람을 말할 수 있습니다. 

우리는 비트 마스크 측면 중 하나를 나타 내기 위해 다른 측면은 약간의 비트 조작을 사용하여 쉽게 찾을 수 있습니다. 세 사람이 있다는 점을 고려할 때 '3'크기의 비트 마스크를 사용하여 세 사람을 나타냅니다. 한 사람 (두 번째)이 목적지 측에있는 경우. 초기 쪽을 나타내는 비트 마스크는 3이되고 대상 쪽의 비트 마스크는 (2 < 무료(초기면을 나타내는 비트 마스크). 따라서 (2 ^ n-1) XOR (5) = 7 XOR 5 = 2.

이제 우리는 2 차원 동적 프로그래밍 dp [mask] [이동 방향], 여기서 mask는 마스크를 대표하는 사람을 왼쪽에서 오른쪽 (이동 방향 = 0) 또는 오른쪽에서 왼쪽 (이동 방향 = 1)으로 이동하는 데 필요한 최소 시간을 나타냅니다.

암호

Bridge 및 Torch 문제에 대한 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 및 Torch 문제에 대한 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)

우리는 2 ^ n에 기여하는 N 개의 숫자를 나타 내기 위해 비트 마스크를 사용하고 있습니다. 그런 다음 N ^ 2의 계수를 제공하는 두 개의 중첩 루프를 사용하여 각 쌍을 확인합니다. 따라서 시간 복잡도는 O (2 ^ N * N ^ 2)입니다.

공간 복잡성: O (2 ^ N)

여기서는 비트 마스크보다 Dp를 사용하고 있습니다. 그리고 DP 배열은 방향과 비트 마스크에 의존하기 때문에 방향이 2 개뿐입니다. 우리는 O (2 ^ N)의 지수 공간 복잡도를 가지고 있습니다.

Translate »