算法第五章总结

回溯，实质是一个一个去试，看看这种方法能不能成功，如果不能成功就退回去再去试，以此类推，一般采用树的数据结构（不是真树，只需要有一个类树向量就行了）

回溯效率相比来说比较低，但是可以用限界/剪枝函数对他优化。

我们这里来总结回溯题型的一般分类。

1.全0 1向量

顾名思义，这类问题的解向量只由0，1构成，多见于一些筛选类问题。如：0-1背包问题。

一般这类问题的剪枝方法都是在不选这个物品时候看看如果其他物品全选看看有没有可能达到最优解，如果无法达到最优解【或者能达到解】就直接剪枝。【实际上0-1背包问题的宽剪枝具有普遍性，严剪枝没有】特点是在回溯（t+1）层之前可以不做操作直接回溯。

每个问题的限界函数办法由题目本身决定。

5-3 部落卫队问题 (25 分)

原始部落byteland中的居民们为了争抢有限的资源，经常发生冲突。几乎每个居民都有它的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。

输入格式:

第一行两个正整数n和m，表示byteland部落中有n个居民，居民间有m个仇敌关系， 0<n<200, 0<m<6000。居民编号为1,2,…,n。接下来输入m行中，每行正整数u和v，表示居民u和居民v是仇敌。

输出格式:

输出部落卫队最佳组建方案中包含的居民人数。之后逐个输出卫队组成xi, 1<=i<=n, xi=0表示居民i不在卫队中，xi=1表示居民i在卫队中。

输入样例:

输出样例:

3
1 0 1 0 0 0 1 
这题实际上是选人，在选每个人之前看看他会不会和其他人有仇，剪枝方法是看如果不选这个人能不能招募到最大数目的兵员。由于这题选上了兵员数就加一，计算方法简单些所以不需要bound

#include<iostream>
using namespace std;
int bytelander;//总人数
int choudi[200][200];//是否互相仇敌关系
int soldier[200];//当前方案
int bestsoldier=0,bestchoice[200],sumsoldier=0;//带best的是最佳，sumsoidler是当前的总人数
bool check(int t)
{
    for(int i=0;i<t;i++)
    {
        if(soldier[i] && choudi[i][t])
        {
            return false;
        }
    }
    return true;
}//限界，检查兵员
void backtrack(int t)
{
    if(t>=bytelander)
    {
        if(sumsoldier > bestsoldier)
        {
            bestsoldier=sumsoldier;
            for(int i=0;i<bytelander;i++)
            {
                bestchoice[i] = soldier[i];
            }

        }
        return;
    }
    if(check(t))
    {
        soldier[t]=1;
        sumsoldier++;
        backtrack(t+1);
        //soldier[i]=0;
        sumsoldier--;//注意这里的状态是不是回溯的
    }
    if(sumsoldier+(bytelander-t-1) > bestsoldier)//限界
    {
        soldier[t]=0;
        backtrack(t+1);
    }
}
int main()
{
    cin>>bytelander;
    int i,j,k,n;
    for(i=0;i<199;i++)
    {
        for(j=0;j<199;j++)
        {
            choudi[i][j]=0;
        }
    }
    cin>>n;
    for(k=0;k<n;k++)
    {
        cin>>i>>j;
        i--;
        j--;
        choudi[i][j]=1;
        choudi[j][i]=1;
    }
    backtrack(0);
    cout<<bestsoldier<<endl;
    for(i=0;i<bytelander;i++)
    {
        cout<<bestchoice[i]<<" ";
    }
}

【0-1，作业1，3属于这种题型】

（左边字为选1不？ YN代表0 1）

2.越选越少

选一次就不能再选。一般都是题目不能重复的题目。经典题目如：售货员走城市。
向量由一堆不重复的1-n数构成
如何保证不重复？
1.swap法
建立一个开局顺序的数组，一旦哪个元素确定就要把该元素调到对应位置，同时对现有元素进行交换
如：售货员问题中，一开始走的（1，2，3，4），如果先去3则排第二位的2和3交换，得到（1，3，2，4），2，4刚好还没去
2.bool法
建立一个boolean数组，一旦这个被使用过要置true同时限界【注意：回溯时候要回溯回来】
剪枝：看加过这个值之后会不会和最优解偏离

5-2 工作分配问题 (50 分)

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。

输入格式:

输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。

输出格式:

将计算出的最小总费用输出到屏幕。

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

9
【这里用的bool法限界。】因为由题目可知，一个人只能打一份工，越用越少，所以不解释。

#include<iostream>
using namespace std;
int sumpeople,salary=0,minsalary=1000000;
int work[21][21];//存储c
bool employ[21];//用于限界
void backtrack(int t)
{
    if(t>sumpeople)
    {
        if(salary<minsalary)
        {
            minsalary=salary;
        }
        return;
    }
    for(int i=1;i<=sumpeople;i++)
    {
        if(!employ[i]&& salary+work[t][i]<minsalary)
        {
            employ[i]=true;
            salary+=work[t][i];
            backtrack(t+1);
            salary-=work[t][i];
            employ[i]=false;//注意：这个值也要回溯否则报错
        }


    }
}
int main()
{
    int i,j;
    cin>>sumpeople;
    for(i=1;i<=sumpeople;i++)
    {
        for(j=1;j<=sumpeople;j++)
        {
            cin>>work[i][j];
        }
        employ[i]=false;
    }
    backtrack(1);
    cout<<minsalary;
}

（字为第一份工选）

3.多选一

对于每个任务，都有多种不同的解决方式供选择，且解决方式数量总相等。用向量解就是（0~n，0~n，...）例：n皇后

这种一般写限界/剪枝很重要，否则效率会很低【甚至部分极端题目需要完全靠限界剪枝给解】

这里的限界剪枝一般都需要透过因素看本质，认清哪个因素是用于限界，哪个因素用于筛选最优解【有些题目这些点会省略】，然后就没有然后了~~

5-4 最小重量机器设计问题 (25 分)

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j 处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过d的最小重量机器设计。

输入格式:

第一行有3 个正整数n ，m和d， 0<n<30, 0<m<30, 接下来的2n 行，每行n个数。前n行是c，后n行是w。

输出格式:

输出计算出的最小重量，以及每个部件的供应商

输入样例:

输出样例:

在这里给出相应的输出。例如：

4
1 3 1

限界因素：价值//必要

剪枝因素：重量//最佳

#include<iostream>
using namespace std;
int producer,elem,maxprice,value[100][100],weight[100][100],bestprocess[100],sumvalue=0,sumweight=0,minweight=100000,process[100];//elem物品数，producer厂商数，process记录最佳情况
void backtrack(int t)
{
    int i;
    if(t>elem)
    {
        if(sumweight < minweight)
        {
            minweight=sumweight;
            for(i=1;i<=elem;i++)
            {
                bestprocess[i]=process[i];
            }
        }
        return;

    }

    for( i=1;i<=producer;i++)
    {
        if(sumvalue+value[t][i] <= maxprice && sumweight+weight[t][i] <= minweight)//左边限界，右边剪枝
        {
            process[t]=i;
            sumweight+=weight[t][i];
            sumvalue+=value[t][i];
            backtrack(t+1);
            sumweight-=weight[t][i];
            sumvalue-=value[t][i];
        }

    }
}
int main()
{
    cin >> elem >> producer >> maxprice;
    int i,j;
    for(i=1;i<=elem;i++)
    {
        for(j=1;j<=producer;j++)
        {
            cin>>value[i][j];
        }
    }
    for(i=1;i<=elem;i++)
    {
        for(j=1;j<=producer;j++)
        {
            cin>>weight[i][j];
        }

    }
    backtrack(1);
    cout<<minweight<<endl;
    for(i=1;i<=elem;i++)
    {
        cout<<bestprocess[i]<<" ";
    }
}

本次组队编程情况：这次主要是我在打代码...然后讲还差点没讲懂我高估我队友水平了= =