计算机算法课---回溯(整数变换问题、子集和问题、工作分配问题)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了计算机算法课---回溯(整数变换问题、子集和问题、工作分配问题)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3784字，纯文字阅读大概需要6分钟。

内容图文

题目

1.整数变换问题

整数i的两种变换定义为 ， （向下取整）；设计一个算法求给定两个整数a和b，用最少次数的 和 变换将整数a变换为b；例如
实现提示：
观察f和g两个操作可知，f总是使得i变大，g总是使得i变小。因此在决定让x执行哪个操作之前可以先判断i和目标值m之间的大小关系。如果x>m，就让其执行g操作；反之，执行f操作。
问题的解分为两种情况，一种是有解，即n可以通过函数变换成m；另一种是无解，即n无法通过函数变换成m。
有解的情况比较容易，只需要判断最后的i是否等于m即可。如果i等于m，那么说明n已经被变换成m了，递归返回。无解的情况可用下例分析。假设我们的输入n=9,m=5。

n>m,执行g,n=[9/2]=4
n<m,执行f,n=34=12
n>m,执行g,n=[12/2]=6
n>m,执行f,n=[6/2]=3
n<m,执行g,n=33=9
n>m,执行f,n=[9/2]=4

如果n的值陷入了一个重复的循环，如果在递归的过程中，出现了前面计算过的元素，那就说明n是无法转换成m的。这种方法实现稍微复杂，需要判断当前所求出的数值之前是否出现过。 另一种简单的处理方式： 对于m无论如何变换都不能变为n的情况，可以加一个判断条件，比如深度达一个较大值为止（如1000）。回溯法， 用子集树实现，子集树结构为：

回溯返回条件有两个，一个是i等于m，另一个是出现了重复的数字。第二个返回条件可以用一个函数test来判断。

剪枝条件：

显式约束：如果x>m，就剪掉它的左子树；如果x<m，就剪掉它的右子树；
隐式约束：如果在某次计算的过程中发现当前的计算次数已经大于或等于最少计算次数了，那么就剪掉这个分支。

#include <iostream>

using namespace std;
/**
*整数i的两种变换定义为 ， （向下取整）；设计一个算法求给定两个整数a和b，用最少次数的 和 变换将整数a变换为b；例如
实现提示：
观察f和g两个操作可知，f总是使得i变大，g总是使得i变小。因此在决定让x执行哪个操作之前可以先判断i和目标值m之间的大小关系。如果x>m，就让其执行g操作；
反之，执行f操作。
问题的解分为两种情况，一种是有解，即n可以通过函数变换成m；另一种是无解，即n无法通过函数变换成m。
有解的情况比较容易，只需要判断最后的i是否等于m即可。如果i等于m，那么说明n已经被变换成m了，递归返回。
*/
int fn[1001];//0=f,1=g
int arr[1001];//存放计算结果
int cnt = 0;
int test(int n)
{
   for(int i=0;i<cnt-1;i++)
       if(arr[i]==n)return 0;

   return 1;
}
void display(int n,int m)
{
   cout<<m<<"=";
   for(int i=cnt-1;i>=0;i--)
       if(fn[i]==1)cout<<"g";
       else cout<<"f";
   cout<<"("<<n<<")"<<endl;
}
void dfs(int n,int m,int num)
{
   if(n==m)
   {
       display(num,m);
       return ;
   }
   else
   {


       if(n>m){n=n/2;fn[cnt]=1;}
       else n=n*3;
       arr[cnt++]=n;

       if(test(n)&&cnt<1000)dfs(n,m,num);
       else {
           cout<<"无解"<<endl;
           return;
       }
   }
}
int main()
{
   int n,m;
   cin>>n>>m;
   dfs(n,m,n);
   return 0;
}

2. 子集和问题

问题描述：给定集合S，S中有n个正整数，M是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中各元素之和等于M。请设计回溯法求解子集和问题，如果问题无解，输出“No Solution”,问题有解，则输出满足子集S1中各元素的值。

#include <iostream>

using namespace std;
int arr[1001];
int dp[1001];
int sum=0;
int cnt=0;
void dfs(int n,int m,int k)
{

   if(sum>m||k>n)return;
   if(sum==m)
   {
       cnt++;
       for(int i=0;i<n;i++)
           if(dp[i])cout<<arr[i]<<" ";
       cout<<"\n";

   }
   else
       for(int i=0;i<2;i++)
           if(i==0){
               sum+=arr[k];
               dp[k]=1;
               dfs(n,m,k+1);
               dp[k]=0;
               sum-=arr[k];
           }
           else dfs(n,m,k+1);

}
int main()
{
   int n,m;
   cin>>n>>m;
   for(int i=0;i<n;i++)
   {

       cin>>arr[i];

   }
   dfs(n,m,0);
   if(cnt==0)cout<<"No Solution"<<endl;
   return 0;
}

3. 工作分配问题。

问题描述：设有n件工作分配给n个人。将工作i分配给第j个人的费用为cij,请设计算法，为每个人都分配1件不同的工作，并使得总费用达到最小。
实现提示：该问题的解空间是一棵排列树，可用搜索排列树的回溯框架实现。

#include <iostream>

using namespace std;
/***
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。
设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。
*/
int arr[22][22];
int minCost = 9999;
int sumCost = 0;
int vis[22];//工人个数
void dfs(int k,int n)
{
    if(k==n)
    {
        if(sumCost<minCost)minCost=sumCost;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            sumCost+=arr[k][i];
            if(vis[i]!=1&&sumCost<minCost)
            {
                vis[i]=1;
                dfs(k+1,n);
                vis[i]=0;
            }
            sumCost-=arr[k][i];
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>arr[i][j];
    dfs(0,n);
    cout<<minCost<<endl;
    return 0;
}

内容总结

以上是互联网集市为您收集整理的计算机算法课---回溯(整数变换问题、子集和问题、工作分配问题)全部内容，希望文章能够帮你解决计算机算法课---回溯(整数变换问题、子集和问题、工作分配问题)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---