Програма для проблеми міст та факел


Рівень складності Жорсткий
Часто запитують у Accolite eBay Quora Snapdeal Терадата Times Інтернет
масив Динамічне програмування

Постановка проблеми

Проблема "Міст і смолоскип" стверджує, що вам дається безліч часу, необхідного людині, щоб перетнути міст. Оскільки це час, він містить цілі натуральні числа. Разом із часом нам дають міст, який людині потрібно пройти. Міст дозволяє одночасно переходити лише двом людям. Вони несуть факел під час переправи. А оскільки там є один факел. Хтось із людей з іншого боку повинен повернутися і віднести факел назад на вихідну сторону. Коли дві людини переходять міст, вони можуть переходити зі швидкістю повільнішої людини. Знайдіть мінімальний загальний час, за який усі люди можуть перетнути міст.

Приклад

Програма для проблеми міст та факел

timeToCross = {1, 2, 3}
6

Пояснення: Спочатку людина 1 та 2 перетинають міст. Отже, до цього часу минуло 2 секунди. Тепер людина 1 переходить або повертається назад на стартову сторону. Потім людина 2 і 3 перетинають міст. Таким чином, загальний витрачений час = 2 + 1 + 3 = 6.

Підхід до проблеми мосту та факелів

Наївний підхід

Ми можемо використовувати рекурсію, щоб написати програму для проблеми мосту та факела, щоб знайти все перестановкаs часу перетинання масиву. Потім спочатку ми переносимо двох людей з одного боку на інший за допомогою факела. Тоді найшвидша людина з іншої (цільової) сторони повертається назад на початкову сторону. Роблячи це, ми можемо знайти мінімальний час, необхідний для пересилання всіх осіб з одного боку на інший, що відповідають всім умовам.

Але цей алгоритм вимагає експоненціального часу для запуску. Таким чином, необхідний ефективний підхід.

Ефективний підхід

Ми можемо написати програму для проблеми містків та факелів, використовуючи ефективний підхід динамічне програмування оскільки ми можемо розділити початкову задачу на менші підзадачі, які можна далі поділити на менші підзадачі. Отже, замість того, щоб обчислювати чи вирішувати менші підзадачі кілька разів. Ми збережемо результат, а потім об’єднаємо ці результати, щоб знайти свою відповідь. 

Вирішуючи цю проблему, слід зауважити кілька речей. Коли дві людини перетинають міст, використовується швидкість повільнішої людини. Факел потрібно повернути назад на початкову сторону. Тепер нам потрібно представити людей з лівого та правого боку. Ми також можемо сказати осіб на початковій стороні та стороні призначення. 

Ми будемо використовувати bitmask представляти одну зі сторін, а іншу сторону можна легко знайти, використовуючи деякі бітові маніпуляції. Враховуючи, що у нас троє людей, ми використовуємо бітову маску розміром «3» для представлення трьох людей. Якщо одна особа (3-а) знаходиться на стороні призначення. Бітова маска, яка представляє початкову сторону, буде 2, бітова маска для сторони призначення = (101 < XOR(бітова маска, що представляє початкову сторону). Таким чином (2 ^ n-1) XOR (5) = 7 XOR 5 = 2.

Тепер ми будемо використовувати 2-мірна Динамічне програмування dp [маска] [напрямок руху], де маска являє собою мінімальний час, необхідний для переміщення людини, що представляє маску, зліва направо (напрямок руху = 0) або справа наліво (напрямок руху = 1),

код

Код C ++ для проблеми Bridge та 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)

Ми використовуємо бітову маску для представлення N чисел, що сприяє 2 ^ n. А потім перевіряємо кожну пару, використовуючи два вкладені цикли, які дають нам коефіцієнт N ^ 2. Таким чином, часова складність становить O (2 ^ N * N ^ 2).

Складність простору: O (2 ^ N)

Тут ми використовуємо Dp поверх бітової маски. А оскільки наш масив DP залежить від напрямку та бітової маски, де є лише 2 напрямки. Ми маємо експоненціальну просторову складність O (2 ^ N).