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) |
|
很有意思的一个题目，大概是说有n个人(1<=n<=6)要过一个独木桥，独木桥每次最多只能过2个人。过桥必须要灯笼，而且只有一盏灯笼。如果2个人一起过桥，所花时间由那个需要最长时间的人决定。问怎么过桥所需要的时间最短。
由于题目的数据量不是很大，我直接用dfs搜了下所有的情况然后取最小的时间。貌似还有数学方法能很轻松的解决，不过还没想到。
#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;
}