子集和问题工作分配问题回溯法实验

港控/mmm° 2023-09-28 08:27 117阅读 0赞

实验名称： 回溯法

一、实验预习

1、实验目的

1. 理解并掌握回溯法的设计思想；

2. 提高应用回溯法解决问题和设计算法的能力；

3. 通过编程实现子集和问题和工作分配问题，进一步理解回溯法的深度优先搜索策略和剪枝函数。

2、实验内容

1. 子集和问题：子集和问题的一个实例为〈S, c〉。其中，S=\{x1,x2,…,xn\}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在 S 的一个子集 S1，使得 *x**Î**S1**x=c*![5abef2676c674edb84236ece1f71120f.png][] 。例如，当n=5，c=10，S=\{2 2 6 5 4\}时，结果S1=\{2 2 6\}。对于给定的正整数的集合S=\{x1,x2,…,xn\}和正整数 c，编程计算 S 的一个子集S1，使得 *x**Î**S1**x=c*![31fded1684f04f5fa2302e324786c133.png][] 。

两个测试用例：输入数据分别由文件名为 input 1.txt和input 2.txt的文本文件提供，文件第一行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。请分别计算并给出结果。

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

两个测试用例：输入数据分别由文件名为 input 1.txt和input 2.txt的文本文件提供，文件的第一行有1个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用，请分别计算并给出最小的总费用。

3、硬、软件环境

计算机型号：Windows 11版81FW

编程语言：C++

开发工具：Dev-C++

4、实验预备工作

算法思想：

按深度优先搜索策略，从根结点出发搜索整个解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果不包含，跳过对该结点为根的子树的搜索，继续该结点兄弟结点的搜索。否则，进入该子树，继续按深度优先策略搜索。

适用条件：

当需要找出问题的解集或者要求满足某些约束条件的最优解时, 常使用回溯法，这种方法适用于解一些组合数相当大的问题，如排列、子集。

基本要素：

深度优先搜索、剪枝函数（约束函数、限界函数）

解题步骤：

(1) 针对所给问题，定义问题的解空间；

(2) 确定易于搜索的解空间结构；

(3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索；

**二、实验报告**

1、实验步骤

问题分析：对于集合S=\{x1,x2,…,xn\}，要找其子集元素之和等于给定数c，那么集合S里的每一个元素都只有两种可能：装入子集，或者不装入子集。明显存在这样的解向量(x1,x2,…,xn)以及解空间树，剪枝条件是当前已求的和大于了给定数c。

设计思想：设一个bool型数组flag\[n\]，flag\[i\] 表示某个元素S\[i\]是否装入要求的子集中，再设个sum表示当前已经加入子集了的元素的和，然后sum每更新一次就比较一次是否等于c了，小于就继续添加元素，大于了就剪掉此子树的搜索，换下一个兄弟字树，等于了则输出子集，再用个变量flagxx标记搜索结束，结束其他搜索。若函数结束flagxx没变，说明没找到这样的子集。

代码描述：

![d8c0ec47fbeb4b9a8bef6c9e1b6c7168.png][] 标题

2、实验结果

1、第一问：

#include <iostream>
    using namespace std;
    int S[100];
    bool flag[100],flagxx=true;
    
    void DFS(int i,int n,int c,int sum){
        if((i>n||sum>c)&&flagxx)
            return;
        else if(sum==c){          //判断结果如何，满足则输出
            cout<<"找到一个子集S1："<<endl;
            for(int i=0; i<n; i++){
                 if(flag[i])
                 cout<<S[i]<<" ";
            }
            cout<<endl;
            flagxx=false;
        }
        else{
            sum+=S[i];        //S[i]装入子集，开始下一个
            flag[i]=true;   
            DFS(i+1,n,c,sum);                             
            sum-=S[i];        // S[i]不装入子集，继续下一个
            flag[i]=false;
            DFS(i+1,n,c,sum);   
        }
    }
    
    int main(){  
        int n,c,sum=0;
        cin>>n>>c;
        for(int i=0; i<n; i++){
            cin>>S[i];
            flag[i]=false;
        }
        DFS(0,n,c,sum);
        if(flagxx) cout<<"不存在这样的子集"<<endl;  
        return 0;
    }

![0ef6e22affeb4ab5b65f9d3d685eff61.png][] ![61c59d4d84284731af461ccbe09a9900.png][]

2、第二问：

#include <iostream>
    using namespace std;
    int min_pay=9999999,c[100][100];
    bool flag[100]; 
    
    void DFS(int i,int n,int sum_pay){
        if(i==n && min_pay>sum_pay){
            min_pay=sum_pay;
            return;
        }
        for(int j=0; j<n; j++){   //为第 i个工作选人
            if(!flag[j]){
                flag[j]=1;  
                sum_pay+=c[i][j];
                if(sum_pay<min_pay)
                    DFS(i+1,n,sum_pay);   //当前总费用不到 min_pay，继续分配下一个
                flag[j]=0;
                sum_pay-=c[i][j];
            }
        }
    }
    
    int main(){
            int n,sum_pay=0;
        cin>>n;
        for(int i=0; i<n; i++){
            flag[i]=false;      
            for(int j=0; j<n; j++)      
                cin>>c[i][j];
        }
        DFS(0,n,sum_pay);
        cout<<"总费用最小为："<<min_pay<<endl;
        return 0;
    }

![57081c9a6ce64634a092e03d2ccfc55c.png][] ![fc38fe652051448aa9334293e78ae03d.png][]

3、实验结论

……………………（懒）……………………

[5abef2676c674edb84236ece1f71120f.png]: https://img-blog.csdnimg.cn/5abef2676c674edb84236ece1f71120f.png
[31fded1684f04f5fa2302e324786c133.png]: https://img-blog.csdnimg.cn/31fded1684f04f5fa2302e324786c133.png
[d8c0ec47fbeb4b9a8bef6c9e1b6c7168.png]: https://img-blog.csdnimg.cn/d8c0ec47fbeb4b9a8bef6c9e1b6c7168.png
[0ef6e22affeb4ab5b65f9d3d685eff61.png]: https://img-blog.csdnimg.cn/0ef6e22affeb4ab5b65f9d3d685eff61.png
[61c59d4d84284731af461ccbe09a9900.png]: https://img-blog.csdnimg.cn/61c59d4d84284731af461ccbe09a9900.png
[57081c9a6ce64634a092e03d2ccfc55c.png]: https://img-blog.csdnimg.cn/57081c9a6ce64634a092e03d2ccfc55c.png
[fc38fe652051448aa9334293e78ae03d.png]: https://img-blog.csdnimg.cn/fc38fe652051448aa9334293e78ae03d.png