Bridge and Torch problemi üçün proqram

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Akkolit eBay Quora Snapdeal Teradata Times İnternet
Geyim Dinamik proqramlaşdırmaBaxılıb 27

Problem bəyanat

“Körpü və Məşəl” problemi sizə bir insanın körpüdən keçməsi üçün bir sıra vaxt verildiyini bildirir. Vaxt gəldiyindən, müsbət tam ədədi ehtiva edir. Vaxtla yanaşı, bizə bir insanın keçməsi lazım olan bir körpü verilir. Körpü bir anda yalnız iki nəfərin keçməsinə imkan verir. Onlar keçərkən bir məşəl daşıyırlar. Və tək bir məşəl olduğundan. Qarşı tərəfdəki insanlardan biri qayıtmalı və məşəli yenidən başlanğıc tərəfə aparmalıdır. İki nəfər körpüdən keçəndə daha yavaş bir insanın sürəti ilə keçə bilər. Hər kəsin körpüdən keçə biləcəyi minimum ümumi vaxtı tapın.

misal

Bridge and Torch problemi üçün proqramPin

timeToCross = {1, 2, 3}
6

İzahat: Əvvəlcə 1-ci və 2-ci şəxslər körpüdən keçir. Beləliklə, bu günə qədər 2 saniyə keçdi. İndi 1 nəfər keçib yenidən başlanğıc tərəfə qayıdır. Sonra 2 və 3 nəfər körpüdən keçir. Beləliklə çəkilən ümumi vaxt = 2 + 1 + 3 = 6-dır.

Körpü və məşəl probleminə yanaşma

Sadəlövh yanaşma

Bütün bunları tapmaq üçün körpü və məşəl problemi üçün bir proqram yazmaq üçün rekursiyadan istifadə edə bilərik permütasyonsıra keçmək üçün vaxt. Sonra əvvəl məşəllə iki nəfəri bir tərəfdən digərinə keçiririk. Sonra başqa (təyinatlı) tərəfdən ən sürətli adam yenidən ilkin tərəfə qayıdır. Bunu etməklə, bütün şərtləri təmin edən bütün şəxsləri bir tərəfdən digər tərəfə göndərmək üçün tələb olunan minimum vaxtı tapa bilərik.

Ancaq bu alqoritmin işləməsi üçün eksponent vaxt tələb olunur. Beləliklə, səmərəli bir yanaşma tələb olunur.

Səmərəli yanaşma

Effektiv bir yanaşma istifadə edərək körpü və məşəl problemi üçün bir proqram yaza bilərik dinamik proqramlaşdırma çünki ilkin problemi daha kiçik alt problemlərə bölə bilən kiçik alt problemlərə bölə bilərik. Beləliklə, kiçik alt problemləri bir neçə dəfə hesablamaq və ya həll etmək əvəzinə. Nəticəni saxlayacağıq və sonra cavabımızı tapmaq üçün bu nəticələri birləşdirəcəyik. 

Bu problemi həll edərkən qeyd etmək lazım olan bəzi şeylər var. İki nəfər körpüdən keçəndə daha yavaş adamın sürətindən istifadə olunur. Məşəlin əvvəlki tərəfə qaytarılması lazımdır. İndi sol və sağ tərəfdəki şəxsləri təmsil etməliyik. İlk tərəf və təyinat tərəfindəki şəxsləri də deyə bilərik. 

Biz istifadə edəcəyik bit maskası tərəflərdən birini təmsil etmək və digər tərəfi bəzi bit manipulyasiyalarından istifadə edərək asanlıqla tapmaq olar. Üç nəfər olduğumuzu nəzərə alaraq, 3 nəfəri təmsil etmək üçün '3' ölçülü bitmask istifadə edirik. Bir nəfər (2-ci) təyinat tərəfindədirsə. İlkin tərəfi təmsil edən bitmask 101 olacaq, təyinat tərəfi üçün bitmask = (1 < XOR(başlanğıc tərəfi təmsil edən bitmask). Beləliklə (2 ^ n-1) XOR (5) = 7 XOR 5 = 2.

İndi istifadə edəcəyik 2 ölçülü Dinamik proqramlaşdırma dp [maska] [hərəkət istiqaməti], burada maska ​​maskanı təmsil edən şəxsin soldan sağa (hərəkət istiqaməti = 0) və ya sağdan sola (hərəkət istiqaməti = 1) hərəkət etməsi üçün tələb olunan minimum vaxtı əks etdirir;

Kodu

Bridge və Torch Problemi üçün C ++ kodu

#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 və Torch Problemi üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (2 ^ N * N ^ 2)

2 ^ n-ə kömək edən N sayını təmsil etmək üçün bitmask istifadə edirik. Və sonra bizə N ^ 2 əmsalı verən iki iç içə döngə istifadə edərək hər cütü yoxlayırıq. Beləliklə zamanın mürəkkəbliyi O (2 ^ N * N ^ 2) -dir.

Kosmik Mürəkkəblik: O (2 ^ N)

Burada bitmask üzərində Dp istifadə edirik. DP seriyamız yalnız 2 istiqamətin olduğu istiqamət və bitmaskdan asılı olduğundan. O (2 ^ N) eksponent faza mürəkkəbliyinə sahibik.

Translate »