차례
문제 정책
“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)의 지수 공간 복잡도를 가지고 있습니다.
