Bridgeրագիր կամրջի և ջահի խնդրի համար


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Ակոլիտ eBay Quora Snapdeal Տերադատա Times ինտերնետ
Դասավորություն Դինամիկ ծրագրավորում

Խնդիրի հայտարարություն

«Կամուրջ և ջահ» խնդիրը նշում է, որ ձեզ կտրվի ժամանակի զանգված, որն անհրաժեշտ է մարդուն անցնելու կամուրջը: Քանի որ ժամանակն է, այն իր մեջ ներառում է դրական ամբողջ թվեր: Timeամանակին զուգահեռ մեզ տալիս են կամուրջ, որը մարդն անցնելու կարիք ունի: Կամուրջը միանգամից թույլ է տալիս անցնել միայն երկու մարդու: Անցնելիս նրանք ջահ են տանում: Եվ քանի որ կա մեկ ջահ: Մյուս կողմի մարդկանցից մեկը պետք է վերադառնա և ջահը հետ վերցնի մեկնարկային կողմ: Երբ երկու մարդ անցնում է կամուրջը, նրանք կարող են անցնել ավելի դանդաղ մարդու արագությամբ: Գտեք նվազագույն ընդհանուր ժամանակը, որի ընթացքում բոլոր մարդիկ կարող են անցնել կամուրջը:

Օրինակ

Bridgeրագիր կամրջի և ջահի խնդրի համար

timeToCross = {1, 2, 3}
6

Բացատրություն. Նախ, 1-ին և 2-րդ անձինք անցնում են կամուրջը: Այսպիսով, մինչ այժմ անցել է 2-ը: Այժմ 1 անձը հատում կամ վերադառնում է մեկնարկային կողմ: Այնուհետև 2 և 3 անձինք անցնում են կամուրջը: Այսպիսով, վերցված ընդհանուր ժամանակը = 2 + 1 + 3 = 6:

Մոտեցում կամրջի և ջահի խնդրին

Միամիտ մոտեցում

Մենք կարող ենք օգտագործել ռեկուրսիան ՝ կամուրջ և ջահերի խնդրի ծրագիր գրելու, բոլորն գտնելու համար տեղադրումըզանգվածը հատելու ժամանակի ժամանակները: Հետո նախ ջահով երկու հոգի տեղափոխում ենք մի կողմից մյուսը: Հետո մեկ այլ (նպատակակետ) կողմից ամենաարագ մարդը վերադառնում է նախնական կողմ: Դրանով մենք կարող ենք գտնել բոլոր այն պայմանները բավարարող բոլոր անձանց մի կողմից մյուսը ուղարկելու համար անհրաժեշտ նվազագույն ժամանակը:

Բայց այս ալգորիթմը գործարկման ժամանակ պահանջում է էքսպոնենտալ ժամանակ: Այսպիսով, անհրաժեշտ է արդյունավետ մոտեցում:

Արդյունավետ մոտեցում

Մենք կարող ենք ծրագիր գրել կամրջի և ջահի խնդրի համար ՝ օգտագործելով արդյունավետ մոտեցում, որը կօգտագործվի դինամիկ ծրագրավորում քանի որ մենք կարող ենք նախնական խնդիրը բաժանել ավելի փոքր ենթախնդիրների, որոնք հետագայում կարելի է բաժանել ավելի փոքր ենթախնդիրների: Այսպիսով, փոքր ենթախնդիրները բազմակի անգամ հաշվարկելու կամ լուծելու փոխարեն: Մենք կպահենք արդյունքը և այնուհետև կկազմենք այդ արդյունքները ՝ գտնելու մեր պատասխանը: 

Այս խնդիրը լուծելիս պետք է նշել մի քանի բան: Երբ երկու մարդ անցնում է կամուրջը, օգտագործվում է ավելի դանդաղ անձի արագությունը: Torահը պետք է վերադարձվի նախնական կողմ: Այժմ մենք պետք է ներկայացնենք ձախ և աջ կողմերում գտնվող անձանց: Կարող ենք նաև ասել, որ մարդիկ նախնական և նպատակակետային կողմում են: 

Մենք կօգտագործենք բիտմաս կողմերից մեկը ներկայացնելու համար, իսկ մյուս կողմը հեշտությամբ կարելի է գտնել ՝ օգտագործելով որոշ բիթային մանիպուլյացիաներ: Հաշվի առնելով, որ ունենք երեք հոգի, մենք օգտագործում ենք «3» չափի բիտմակ `3 հոգու ներկայացնելու համար: Եթե ​​մեկ անձ (2-րդ) գտնվում է նպատակակետի կողմում: Սկզբնական կողմը ներկայացնող bitmask- ը կլինի 101, նշանակման կողմի bitmask = (1 < XOR- ը(նախնական կողմը ներկայացնող բիտմաս): Այսպիսով (2 ^ n-1) XOR (5) = 7 XOR 5 = 2:

Հիմա մենք կօգտագործենք Երկչափ Դինամիկ ծրագրավորում dp [դիմակ] [շարժման ուղղություն], երբ դիմակը ներկայացնում է դիմակը ներկայացնող անձին ձախից աջ (շարժման ուղղություն = 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

Բարդության վերլուծություն

Timeամանակի բարդություն: O (2 ^ N * N ^ 2)

Մենք օգտագործում ենք bitmask- ը `N թվերը ներկայացնելու համար, ինչը նպաստում է 2 ^ n- ին: Եվ հետո մենք ստուգում ենք յուրաքանչյուր զույգի համար ՝ օգտագործելով երկու տեղադրված օղակ, որոնք մեզ տալիս են N ^ 2 գործոն: Այսպիսով, ժամանակի բարդությունը O է (2 ^ N * N ^ 2):

Տիեզերական բարդություն՝ O (2 ^ N)

Այստեղ մենք օգտագործում ենք Dp- ի բիթմասը: Եվ քանի որ մեր DP զանգվածը կախված է ուղղությունից և բիտմասից, որտեղ կա ընդամենը 2 ուղղություն: Մենք ունենք O (2 ^ N) տիեզերական բարդության բարդություն: