Problem Statement
|
| |
A well-known riddle goes like this: Four people are crossing an old bridge. The bridge cannot hold more than two people at once. It is dark, so they can't walk without a flashlight, and they only have one flashlight! Furthermore, the time needed to cross the bridge varies among the people in the group. For instance, let's say that the people take 1, 2, 5 and 10 minutes to cross the bridge. When people walk together, they always walk at the speed of the slowest person. It is impossible to toss the flashlight across the bridge, so one person always has to go back with the flashlight to the others. What is the minimum amount of time needed to get all the people across the bridge?
In this instance, the answer is 17. Person number 1 and 2 cross the bridge together, spending 2 minutes. Then person 1 goes back with the flashlight, spending an additional one minute. Then person 3 and 4 cross the bridge together, spending 10 minutes. Person 2 goes back with the flashlight (2 min), and person 1 and 2 cross the bridge together (2 min). This yields a total of 2+1+10+2+2 = 17 minutes spent.
You want to create a computer program to help you solve new instances of this problem. Given an vector <int> times , where the elements represent the time each person spends on a crossing, your program should return the minimum possible amount of time spent crossing the bridge.
|
Definition
|
| |
| Class: |
BridgeCrossing |
| Method: |
minTime |
| Parameters: |
vector <int> |
| Returns: |
int |
| Method signature: |
int minTime(vector <int> times) |
| (be sure your method is public) |
|
很有意思的一個(gè)題目，大概是說有n個(gè)人(1<=n<=6)要過一個(gè)獨(dú)木橋，獨(dú)木橋每次最多只能過2個(gè)人。過橋必須要燈籠，而且只有一盞燈籠。如果2個(gè)人一起過橋，所花時(shí)間由那個(gè)需要最長時(shí)間的人決定。問怎么過橋所需要的時(shí)間最短。
由于題目的數(shù)據(jù)量不是很大，我直接用dfs搜了下所有的情況然后取最小的時(shí)間。貌似還有數(shù)學(xué)方法能很輕松的解決，不過還沒想到。
#include <iostream>
#include <vector>
using namespace std;
class BridgeCrossing
{
public:
int len,time,cross[6],best;
void dfs(int n,bool flash,vector<int> times);
int minTime(vector<int> times);
};
void BridgeCrossing::dfs(int n, bool flash, vector<int> times){
if(n==0){
best=(best>time)?time:best;
return;
}
if(flash){
for(int i=0;i<len;i++)
for(int j=i+1;j<len;j++)
if(cross[i] && cross[j]){
cross[i]=cross[j]=false;
time+=max(times[i],times[j]);
dfs(n-2,!flash,times);
time-=max(times[i],times[j]);
cross[i]=cross[j]=true;
}
}
else{
for(int i=0;i<len;i++)
if(!cross[i]){
cross[i]=true;
time+=times[i];
dfs(n+1,!flash,times);
time-=times[i];
cross[i]=false;
}
}
}
int BridgeCrossing::minTime(vector<int> times){
best=INT_MAX;
len=times.size();
time=0;
for(int i=0;i<6;i++) cross[i]=true;
if(len==1) best=times[0];
else dfs(len,true,times);
return best;
}