ACM中的工作分配问题是一个典型的回溯问题,利用回溯思想能很准确地得到问题的解。下面就这个问题好好分析下。
问题描述:
设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法,计算最佳工作分配方案,为每一个人都分配1 件不同的工作,并使总费用达到最小。
解题思路:
由于每个人都必须分配到工作,在这里可以建一个二维数组c[i][j],用以表示i号工人完成j号工作所需的费用。给定一个循环,从第1个工人开始循环分配工作,直到所有工人都分配到。为第i个工人分配工作时,再循环检查每个工作是否已被分配,没有则分配给i号工人,否则检查下一个工作。可以用一个一维数组x[j]来表示第j号工作是否被分配,未分配则x[j]=0,否则x[j]=1。利用回溯思想,在工人循环结束后回到上一工人,取消此次分配的工作,而去分配下一工作直到可以分配为止。这样,一直回溯到第1个工人后,就能得到所有的可行解。在检查工作分配时,其实就是判断取得可行解时的二维数组的一下标都不相同,二下标同样不相同。
样例分析:
给定3件工作,i号工人完成j号工作的费用如下:
10 2 3
2 3 4
3 4 5
假定一个变量count表示工作费用总和,初始为0,变量i表示第i号工人,初始为1。n表示总的工作量,这里是取3。c[i][j]表示i号工人完成j号工作的费用,x[j]表示j号工作是否被分配。算法如下:
void work(int i,int count){
if(i>n)
return ;
for(int j=1;j<=n;j++)
if(x[j] == 0){
x[j] = 1;
work(i+1,count+c[i][j]);
x[j] = 0;
}
}
那么在这里,用回溯法的思想就是,首先分配的工作是:
10:c[1][1] 3:c[2][2] 5:c[3][3] count=18;
此时,所有工人分配结束,然后回溯到第2个工人重新分配:
10:c[1][1] 4:c[2][3] 4:c[3][2] count=18;
第2个工人已经回溯到n,再回溯到第1个工人重新分配:
2:c[1][2] 2:c[2][1] 5:c[3][3] count=9;
回溯到第2个工人,重新分配:
2:c[1][2] 4:c[2][3] 3:c[3][1] count=9;
再次回溯到第1个工人,重新分配:
3:c[1][3] 2:c[2][1] 4:c[3][2] count=9;
回溯到第2个工人,重新分配:
3:c[1][3] 3:c[2][2] 3:c[3][1] count=9;
这样,就得到了所有的可行解。而我们是要得到最少的费用,即可行解中和最小的一个,故需要再定义一个全局变量cost表示最终的总费用,初始cost为c[i][i]之和,即对角线费用相加。在所有工人分配完工作时,比较count与cost的大小,如果count小于cost,证明在回溯时找到了一个最优解,此时就把count赋给cost。
到这里,整个算法差不多也快结束了,已经能得到最终结果了。但考虑到算法的复杂度,这里还有一个剪枝优化的工作可以做。就是在每次计算局部费用变量count的值时,如果判断count已经大于cost,就没必要再往下分配了,因为这时得到的解必然不是最优解。
#include<iostream>
using namespace std;
int n,cost=0;
int x[100],c[100][100];
void work(int i,int count){
if(i>n && count<cost){
cost = count;
return ;
}
if(count<cost)
for(int j=1;j<=n;j++)
if(x[j] == 0){
x[j] = 1;
work(i+1,count+c[i][j]);
x[j] = 0;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c[i][j];
x[j] = 0;
}
cost+=c[i][i];
}
work(1,0);
cout<<cost<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
这段代码是算法设计与分析中,工作分配问题的完整代码,已经验证过正确性了
C语言资源分配问题代码,算法设计与分析课程中的
基于改进粒子群算法的机位分配问题研究,陈骁睿,杨旭东,为提高机场的运营效率和保证客户的满意度需要合理进行停机位分配工作。经详细分析机位分配问题的要素和约束条件,以停机位使用最
一些研究基于统计学和数学模型,利用数据分析和优化算法来实现宿舍分配的优化。然而,传统的方法主要依赖于人工决策和经验,存在着效率低下、主观性强等问题。因此,研究者开始尝试引入聚类算法来改进宿舍分配的方法...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
试设计一个算法,计算最佳工作分配方案,为每一个人都分配1 件不同的工作,并使总费用达到最小。 41、 编写程序求解骑士巡游问题:在n行n列的棋盘上(如n=8),假设一位骑士(按象棋中“马走日”的行走法)从初始...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
该算法思想是按照进入就绪队列的先后次序来分配处理机。FCFS采用非剥夺调度方式,即一旦某个进程占有处理机,就一直运行下去,直到该进程完成其工作或因等待某一事件而不能继续执行时才释放处理机。 算法实现原理...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
最后, 本文通过一组算例分析, 验证了改进的差分进化算法对大规模问题的有效性, 说明救灾物资的最大允许运输时间和地区间合作的关系. 论文的研究成果对基于属地管理的灾区自救和互救决策具有重要的理论和实践指导...
为了填补这一领域的空白,本文对TOBM问题的代表性算法进行了综合评价和分析。我们首先给出我们统一的定义,然后为所有算法提供统一的实现。最后,基于合成数据集和真实数据集的实验结果,从短期效果和长期效果两个...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
分治思想 众数问题,有重复元素的排列问题,排列的字典序问题,整数因子分解问题...子集和问题,整数变换问题,工作分配问题,部落卫队问题; 分支限界法 运动员最佳匹配问题,n皇后问题; 详细大算法证明和纯正的编码
认知无线网络(CRN)在underlay工作模式下的多用户下行功率分配和波束赋形问题研究中存在通用的SDR算法计算复杂度高、实用性受限以及优化问题中忽视主网络(PN)对认知用户(SU)的干扰等问题。针对这些问题,首先在...