问题
小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每 次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会 熄灭。问：小明一家如何过桥？
分析
为了最短时间过桥，尽量每次用时最短的返回。
首先，第一快与第二快先过。
中间是第一快依次去接剩余中最快的。
倒数第二组是第一慢与第二慢一起过桥。
最后第二快的去接第一快的。
主要证明，为何这样是最省时间的。
每次过桥分为两部分：两人过桥一人返程，两部分时间之和是这次的总共耗时。
每次一定是这种过桥时间最短是局部最优解，所有局部最优解之和是全局最优解。
所以第一次是第一快和第二快先过桥，第一快返回。
情况一
第一快走两趟，去接第三快和第四快。
情况二
第三快和第四快一起走，第三快返回再与第一快过桥。
这两种情况取用时最少的那种情况。
依次类推，至到全部过桥。
- 详细版：保留中间过桥信息
#include <iostream>
#include <vector>
#include <deque>
#include <iterator>
#include <algorithm>
using namespace std;
void PrintCross(int a,int b){
cout << "Cross:" << a << "," << b << endl;
}
void PrintBack(int a){
cout << "Back:" << a << endl;
}
void PrintVec(vector<int> const& vec){
cout << "vec:";
copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
cout << endl;
}
int CrossBridge(vector<int> vec){
if(vec.empty()) return 0;
sort(vec.begin(),vec.end());
PrintVec(vec);
deque<int> uncross(vec.begin(),vec.end());
int min1st = uncross.front();
uncross.pop_front();
// 只有一个人过桥的情况
if(uncross.empty()) return min1st;
int min2nd = uncross.front();
uncross.pop_front();
int spend(0);
// 第一次过桥
PrintCross(min1st,min2nd);
spend = min2nd;
while(!uncross.empty()){
// 最快返回
PrintBack(min1st);
spend += min1st;
// 最慢的优先过桥
int max1st = uncross.back();
uncross.pop_back();
if(uncross.empty()){ // 如果只有一个最后一次过桥
PrintCross(min1st,max1st);
spend += max1st;
}else{ // 每次最慢与次慢过桥，次快返回
int max2st = uncross.back();
uncross.pop_back();
PrintCross(max1st,max2st);
PrintBack(min2nd);
PrintCross(min1st,min2nd);
spend += max1st + min2nd*2;
}
}
return spend;
}
int main(){
cout << CrossBridge({1,3,6,8,12}) << endl;
cout << CrossBridge({1,3,6,8}) << endl;
cout << CrossBridge({1,3,6}) << endl;
cout << CrossBridge({1,3}) << endl;
cout << CrossBridge({1}) << endl;
cout << CrossBridge({}) << endl;
}
- 精简版：删除中间过桥信息
#include <iostream>
#include <vector>
#include <deque>
#include <iterator>
#include <algorithm>
using namespace std;
int CrossBridge(vector<int> vec){
if(vec.empty()) return 0;
sort(vec.begin(),vec.end());
deque<int> uncross(vec.begin(),vec.end());
int min1st = uncross.front();
uncross.pop_front();
// 只有一个人过桥的情况
if(uncross.empty()) return min1st;
int min2nd = uncross.front();
uncross.pop_front();
int spend(0);
// 第一次过桥
spend = min2nd;
while(!uncross.empty()){
// 最快返回
spend += min1st;
// 最慢的优先过桥
int max1st = uncross.back();
uncross.pop_back();
if(uncross.empty()){ // 如果只有一个最后一次过桥
spend += max1st;
}else{ // 每次最慢与次慢过桥，次快返回
int max2st = uncross.back();
uncross.pop_back();
spend += max1st + min2nd*2;
}
}
return spend;
}
int main(){
cout << CrossBridge({1,3,6,8,12}) << endl;
cout << CrossBridge({1,3,6,8}) << endl;
cout << CrossBridge({1,3,6}) << endl;
cout << CrossBridge({1,3}) << endl;
cout << CrossBridge({1}) << endl;
cout << CrossBridge({}) << endl;
}
待加分析说明，如有问题请留言
