期末复习——回溯法

Myth丶恋晨 2022-06-02 02:50 169阅读 0赞

【1】装载问题

问题描述：  
有两艘船，载重量分别是c1、 c2，n个集装箱，重量是wi (i=1…n)，且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。  
输入：  
多个测例，每个测例的输入占两行。第一行一次是c1、c2和n（n<=10）；第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。  
输出：  
对于每个测例在单独的一行内输出Yes或No。  
输入样例：  
7 8 2  
8 7  
7 9 2  
8 8  
0 0 0  
输出样例：  
Yes  
No

#include <iostream>  
    
    using namespace std;  
    
    int calculate(int *goods, int goodsNumber, int maxWight, int nowWight, int nowMax)  
    {  
        int i;  
        int interim = 0;  
        for(i = goodsNumber - 1; i >= 0; i--)  
        {  
            if(nowWight + goods[i] <= maxWight && goodsNumber - 1 >= 0)  
            {  
                if(nowWight + goods[i] > nowMax)  
                {  
                    nowMax = nowWight + goods[i];  
                }  
                interim = calculate(goods, i, maxWight, nowWight + goods[i], nowMax);  
                if(interim > nowMax)  
                {  
                    nowMax = interim;  
                }  
            }  
        }  
        return nowMax;  
    }  
    
    int main()  
    {  
        int maxWight_1, maxWight_2, goodsNum;  
        int interim;  
        int *goods;  
        while(1)  
        {  
            cin >> maxWight_1>> maxWight_2>> goodsNum;  
            if(maxWight_1 == 0)  
            {  
                break;  
            }  
    
            goods = new int[goodsNum];  
            for(int i = 0; i < goodsNum; i++)  
            {  
                cin >> goods[i];  
            }  
            interim = calculate(goods, goodsNum, maxWight_1, 0, 0);  
            if(maxWight_1 + maxWight_2 - interim <= maxWight_2)  
            {  
                cout << "Yes"<< endl;  
            }  
            else  
            {  
                cout << "No"<<endl;  
            }  
        }  
    
        return 0;  
    }

【2】批处理作业调度  
给定 n 个作业的集合 J=\{J1,J2,……..,Jn\} 每个作业 Ji 都有两项任务分别在2台机器上完成，每个作业必须由机器1处理，再由机器2处理，作业 Ji 需要机器 j 的处理时间 tji ,i=\{1,2,3,,,,,,,,n\}。j=1，2。对于一个确定的作业调度，设 Fji 是作业 i 在机器 j 上完成处理的时间。则所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。  
批处理作业调度的问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

#include <iostream>
    using namespace std;
    #define MAX 200
    int* x1;//作业Ji在机器1上的工作时间；
    int* x2;//作业Ji在机器2上的工作时间；
    int number=0;//作业的数目；
    int* xOrder;//作业顺序；
    int* bestOrder;//最优的作业顺序；
    int bestValue=MAX;//最优的时间；
    int xValue=0;//当前完成用的时间；
    int f1=0;//机器1完成的处理时间；
    int* f2;//第i阶段机器2完成的时间；
    
    void BackTrace(int k)
    {
        if (k>number)
        {
            for (int i=1;i<=number;i++)
            {
                bestOrder[i]=xOrder[i];
            }
        bestValue=xValue;
        }
        else
        {
            for (int i=k;i<=number;i++)
            {
                f1+=x1[xOrder[i]];
                f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xOrder[i]];
                xValue+=f2[k];
                swap(xOrder[i],xOrder[k]);
                if (xValue<bestValue)
                {
                    BackTrace(k+1);
                }
        swap(xOrder[i],xOrder[k]);
        xValue-=f2[k];
        f1-=x1[xOrder[i]];
            }
        }
    }
    
    int main()
    {
        int i;
        cout<<"请输入作业数目：";
        cin>>number;
        x1=new int[number+1];
        x2=new int[number+1];
        xOrder=new int[number+1];
        bestOrder=new int[number+1];
        f2=new int[number+1];
        x1[0]=0;
        x2[0]=0;
        xOrder[0]=0;
        bestOrder[0]=0;
        f2[0]=0;
    
        cout<<"请输入每个作业在机器1上所用的时间："<<endl;
        for (int i=1;i<=number;i++)
        {
            cout<<"第"<<i<<"个作业=";
            cin>>x1[i];
        }
    
        cout<<"请输入每个作业在机器2上所用的时间："<<endl;
        for (i=1;i<=number;i++)
        {
            cout<<"第"<<i<<"个作业=";
            cin>>x2[i];
        }
        for(i=1;i<=number;i++)
        {
            xOrder[i]=i;
        }
        BackTrace(1);
        cout<<"最节省的时间为："<<bestValue;
        cout<<endl;
        cout<<"对应的方案为：";
        for(i=1;i<=number;i++)
        {
            cout<<bestOrder[i]<<"  ";
        }
        return 0;
    }

【3】n皇后问题  
用n元组X\[1:n\]表示n后问题的解，其中，X\[i\]表示皇后i放在棋盘第 i 行的第 X\[i\] 列。由于不允许将2个皇后放在同一列上，所以解向量中的 X\[i\]  
互不相同，2个皇后不能放在同一条直线上是一个隐约束，如果将 n\*n格的棋盘看作二维方阵，其行号从上到下，列号从左到右编号为1，2，3，，，，，n,从棋盘左上角到右下角的主对角线及其平行线（即斜率为-1的各斜线）上，2个下标值的差（行号减列号）值相等。同理，斜率为+1的每一条斜线上，2个下标值得和（行号+列号）值相等。因此，若2个皇后放置的位置分别为 （i，j）和（k，l），且 i-j=k-l 或 i+j=k+l，则说明2个皇后处于同一直线上。以上2个方程分别等价于 i-k=j-l 和 i-k=l-j。由此可知，只要 |i-k|=|j-l| 成立，就表明2个皇后位于同一斜线上。

Description  
在N\*N的类似国际象棋棋盘上，要放置N个王后，要求任两个王后之间不能互相攻击，也就是任两个王后不共线。 问有多少种摆放的方法？  
Input  
输入为一组整数，每行为一个整数n，n<=10，最后一行是一个0。  
Output  
对每个整数n（不包括结尾行的0），计算摆放王后的方法，并输出方案个数，每个输出占一行。  
Sample Input  
2  
4  
0  
Sample Output  
0  
2

#include<iostream>  
    #include<math.h>
    using namespace std;  
    int i,j,k,l;
    class Queen {  
        friend int nQueen(int);  
    private:  
        bool Place(int k);  
        void Backtrack(int t);  
        int n,     
            *x;      
        long sum;  
    };  
    bool Queen::Place(int k) {  
        for (int j = 1; j < k; j++)  
            if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k]))  
                return false;  
        return true;  
    }  
    
    void Queen::Backtrack(int)
    {
        x[l]=0;
        int k=1;
        while(k>0)
        {
            x[k]+=1;
            while((x[k]<=n)&&!(Place(k))) x[k]+=1;
                if(x[k]<=n)
                if(k==n) sum++;
                else
                {
                    k++;
                    x[k]=0;
                 } 
                 else k--;
        }
     } 
    
    
    int nQueen(int n) {  
        Queen X;  
        X.n = n;  
        X.sum = 0;  
        int* p = new int[n + 1];  
        for (int i = 0; i <= n; i++)  
            p[i] = 0;  
        X.x = p;  
        X.Backtrack(1);  
        delete [] p;  
        return X.sum;  
    }  
    int main() {  
        int n, set;  
        while(scanf("%d",&n)!=0&&n<=10&&n>0)
        {
            set = nQueen(n);  
            printf("%d\n",set); 
        }
    }