四人过桥求最短时间(《算法设计与分析》习题一的第8题) Apare_xzc

四人过桥求最短时间

题意：
《算法设计与分析》习题一的第8题
4个人晚上过桥，每次最多两人并行，只有一个手电筒。
4个人过桥的最快时间分别为1,2,5,10(分钟)
先挑两个人过去，再有个人送回来，然后在过两个人…
直到4个人都过去，求最少的总时间
暴力：
写了一晚上，好累
用两个vector模拟桥两边有哪些人
先dfs处理出4选2，3选2的情况
然后在暴力DFS找时间最短的方案

我的代码

/* Author: xzc 2019/2/26 */
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
int a[10] = {0,1,2,5,10};
vector<pair<int,int> >v[5]; 
void print(pair<int,int>&pr)
{
	cout<<"("<<pr.first+1<<","<<pr.second+1<<") ";
}
int r[5];
void dfs(int M,int st,int x) //总人数，当前人数 
{
	if(x==2) 
	{
		v[M].push_back(make_pair(r[0],r[1]));
		return;
	}
	For(i,st,M-1)
	{
		r[x] = i;
		dfs(M,i+1,x+1); 
	}
} 
int ans; 
void init()
{
	v[2].push_back(make_pair(0,1));
	cout<<"dfs处理出所有4选2,3选2的方案：\n\n"; 
	dfs(4,0,0);
	dfs(3,0,0); 
	For(i,2,4) 
	{
		cout<<i<<"个人里面选两个过河的所有方案为：\n"; 
		for(auto &x:v[i])
			print(x);
		cout<<endl<<endl;	
	}
	ans = 1e5;
}
vector<int> Left,Right;
vector<int>::iterator it;
vector<int> record;
vector<int> res;
void DFS(bool isLeft,int cost) //当前左边的人数,是在左边还是在右边 
{
	int num = Left.size();
	if(num==0)
	{
		int cnt = 0;
		for(auto &x:record)
		{
			if(++cnt%3==0) cout<<"过河, ";
			cout<<x<<" ";
			if(cnt%3==0) cout<<"回去, "; 
		}
		cout<<"过河。\n\n"; 
		if(ans>cost)
		{
			ans = cost;
			res = record;
		}
		return;
	}
	if(!isLeft) //手电在河的对岸 
	{
		sort(Right.begin(),Right.end());
		int add = Right[0];
		
		cost += add; //贪心 
		Right.erase(Right.begin()); 
		Left.push_back(add);  
		sort(Left.begin(),Left.end());
		record.push_back(add);
		
		DFS(!isLeft,cost);
		
		Right.push_back(add);
		sort(Right.begin(),Right.end());
		for(it=Left.begin();*it!=add&&it!=Left.end();++it);
		Left.erase(it);
		sort(Left.begin(),Left.end()); 
		cost -= add;
		record.pop_back();
		//sort(Left.begin(),Left.end()); //erase之后仍然是递减的 
		return;
	}
	//isLeft = true 手电在左边 
	
	for(auto &x:v[num]) //v[num]里面放了num个人里面选两个人的方案 
	{
		int fastman = Left[x.first];
		int slowman = Left[x.second];
		record.push_back(fastman);
		record.push_back(slowman);
		cost += slowman;
		Right.push_back(fastman);
		Right.push_back(slowman);
		sort(Right.begin(),Right.end());
		Left.erase(Left.begin()+x.first);
		Left.erase(Left.begin()+x.second-1); 
		sort(Left.begin(),Left.end());
		
		DFS(!isLeft,cost);
		
		cost -= slowman;
		Left.push_back(fastman);
		Left.push_back(slowman);
		sort(Left.begin(),Left.end());
		for(it=Right.begin();*it!=fastman&&it!=Right.end();++it);
		Right.erase(it);
		for(it=Right.begin();*it!=slowman&&it!=Right.end();++it);
		Right.erase(it);
		record.pop_back();
		record.pop_back();
	}
}
int main()
{
	std::ios::sync_with_stdio(false);
	init();
	For(i,1,4) Left.push_back(a[i]);
	cout<<"\n贪心的策略是每次从右边的对岸往回送手电筒时挑已经过了的最快的人。\n所有方案如下：\n";
	DFS(1,0);
	cout<<"ans = "<<ans<<endl;
	cout<<"最优方案如下：\n";
	int cnt = 0;
	for(auto &x:res)
	{
		if(++cnt%3==0) cout<<"过河, ";
		cout<<x<<" ";
		if(cnt%3==0) cout<<"回去, "; 
	}
	cout<<"过河。\n"; 
	 
	
	return 0;	
} 

答案：

ans = 17
最优方案如下：
1 2 过河, 1 回去, 5 10 过河, 2 回去, 1 2 过河。

输出：

dfs处理出所有4选2,3选2的方案：

2个人里面选两个过河的所有方案为：
(1,2)

3个人里面选两个过河的所有方案为：
(1,2)  (1,3)  (2,3)

4个人里面选两个过河的所有方案为：
(1,2)  (1,3)  (1,4)  (2,3)  (2,4)  (3,4)


贪心的策略是每次从右边的对岸往回送手电筒时挑已经过了的最快的人。
所有方案如下：
 1, 2过河,  1回去,  1, 5过河,  1回去,  1,10过河: 19分钟
 1, 2过河,  1回去,  1,10过河,  1回去,  1, 5过河: 19分钟

 1, 2过河,  1回去,  5,10过河,  2回去,  1, 2过河: 17分钟

 1, 5过河,  1回去,  1, 2过河,  1回去,  1,10过河: 19分钟

 1, 5过河,  1回去,  1,10过河,  1回去,  1, 2过河: 19分钟

 1, 5过河,  1回去,  2,10过河,  2回去,  1, 2过河: 20分钟

 1,10过河,  1回去,  1, 2过河,  1回去,  1, 5过河: 19分钟

 1,10过河,  1回去,  1, 5过河,  1回去,  1, 2过河: 19分钟

 1,10过河,  1回去,  2, 5过河,  2回去,  1, 2过河: 20分钟

 2, 5过河,  2回去,  1, 2过河,  1回去,  1,10过河: 20分钟

 2, 5过河,  2回去,  1,10过河,  1回去,  1, 2过河: 20分钟

 2, 5过河,  2回去,  2,10过河,  2回去,  1, 2过河: 21分钟

 2,10过河,  2回去,  1, 2过河,  1回去,  1, 5过河: 20分钟

 2,10过河,  2回去,  1, 5过河,  1回去,  1, 2过河: 20分钟

 2,10过河,  2回去,  2, 5过河,  2回去,  1, 2过河: 21分钟

 5,10过河,  5回去,  1, 2过河,  1回去,  1, 5过河: 23分钟

 5,10过河,  5回去,  1, 5过河,  1回去,  1, 2过河: 23分钟

 5,10过河,  5回去,  2, 5过河,  2回去,  1, 2过河: 24分钟

另外，这还是ccnu2018新生赛的签到题

我翻出了前会长Y_Cl写的标程，比我写的简短一点

他写的标程

/* ccnu 2018新生赛A题 Author: Y_Cl */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
using namespace std;

int vis[4];
int cost[4]={1,2,5,10};
int Ans;

void go(int time);
void back(int time);

void go(int time)
{
    for (int i=0; i<4; ++i)
        if (vis[i] == 0)
        {
            bool flag=0;
            for (int j=0; j<4; ++j)
                if (i!=j && vis[j] == 0)
                {
                    flag=1;
                    vis[i] = vis[j] = 1;
                    back(time+max(cost[i],cost[j]));
                    vis[i] = vis[j] = 0;
                }
            if (flag == 0) // 鍙墿涓嬩竴鍙┈娌¤繃娌?
            {
                vis[i] = 1;
                back(time+cost[i]);
                vis[i] = 0;
            }
        }
}

void back(int time)
{
    bool flag=0;
    for (int i=0; i<4; ++i)
        if (vis[i] == 0) flag=1;
    if (!flag) 
    {
        Ans=min(Ans,time);
        return ;
    }
    for (int i=0; i<4; ++i)
        if (vis[i] == 1)
        {
            vis[i] = 0;
            go(time+cost[i]);
            vis[i] = 1;
        }
}


int main()
{
    Ans=1000000;
    vis[0] = vis[1] = vis[2] = vis[3] = 0;
    go(0);
    printf("%d\n",Ans);
    return 0;
}