桥梁和火炬问题程序


难度级别
经常问 ol石 易趣 Quora的 Snapdeal Teradata数据 时代互联网
排列 动态编程

问题陈述

“桥梁和火炬”问题表明,您需要一定的时间才能跨过桥梁。 由于时间到了,它包含正整数。 随着时间的流逝,我们得到了一座桥梁,一个人需要跨越。 这座桥一次只能允许两个人越过。 他们穿越时手持火炬。 而且因为只有一个火炬。 来自另一边的一个人应返回并把火炬带回到起点。 当两个人越过桥时,他们可以以较慢的人的速度越过。 找到所有人都可以过桥的最短总时间。

使用案列

桥梁和火炬问题程序

timeToCross = {1, 2, 3}
6

说明:首先,人1和2过桥。 因此,直到现在2秒过去了。 现在,人1越过或返回起点。 然后,人2和3越过桥。 因此,总耗时= 2 +1 + 3 = 6。

桥梁和火炬问题的解决方法

天真的方法

我们可以使用递归为桥和火炬问题编写程序,以找到所有 排列s穿越阵列的时间。 然后,我们首先用火炬将两个人从一侧移到另一侧。 然后,来自另一(目的地)一侧的最快的人返回到初始一侧。 这样做,我们可以找到满足所有条件的将所有人员从一侧转移到另一侧所需的最短时间。

但是此算法需要指数时间才能运行。 因此,需要一种有效的方法。

高效方法

我们可以使用有效的方法编写程序来解决桥梁和火炬问题 动态编程 因为我们可以将初始问题分为较小的子问题,然后可以进一步细分为较小的子问题。 因此,而不是多次计算或求解较小的子问题。 我们将存储结果,然后将这些结果合并以找到答案。 

解决此问题时,需要注意一些事项。 当两个人过桥时,将使用较慢的人的速度。 火炬需要返回到初始侧。 现在,我们需要代表左侧和右侧的人员。 我们也可以说初始方和目的地方的人员。 

我们将使用 位掩码 使用一些位操作可以轻松找到代表一侧的另一侧。 考虑到我们有3个人,我们使用大小为“ 3”的位掩码表示2个人。 如果目的地是一个人(第二个)。 代表初始端的位掩码为101,目标端的位掩码=(1 < XOR(代表初始面的位掩码)。 因此(2 ^ n-1)XOR(5)= 7 XOR 5 = 2。

现在,我们将使用 2维 动态编程 dp [mask] [移动方向],其中mask表示将代表遮罩的人从左向右移动(移动方向= 0)或从右向左移动(移动方向= 1)所需的最短时间,

代码

桥梁和火炬问题的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

桥梁和火炬问题的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)。