请在 下方输入 要搜索的题目:

部落卫队问题。原始部落byteland中的居民们为了争夺有限的资源,经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍,希望从部落的居民中选出最多的居民入伍,并保证队伍中任何2个人都不是仇敌。给定byteland部落中居民间的仇敌关系,编程计算组成部落卫队的最佳方案。

部落卫队问题。原始部落byteland中的居民们为了争夺有限的资源,经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍,希望从部落的居民中选出最多的居民入伍,并保证队伍中任何2个人都不是仇敌。给定byteland部落中居民间的仇敌关系,编程计算组成部落卫队的最佳方案。

发布时间:2024-11-25 13:11:38
推荐参考答案 ( 由 快搜搜题库 官方老师解答 )
联系客服
答案:def Place(t):#t表示当前要判断第t个居民是否能加入卫队 global x,a Ok = True for j in range(1,t): if (x[j] and a[t][j]==1): #a[][]表示仇敌关系的邻接矩阵 Ok=False break return Ok def backtrack (t): global bestx,x,bestn,cn #搜索第i层结点 if (t>n): # 到达叶结点 bestx=x bestn=cn elif (Place(t)): #搜索左子树 x[t]=1 cn += 1 backtrack(t+1) cn -= 1 elif ((cn+n-t)>bestn):#搜索右子树 x[t]=0 backtrack(t+1)
专业技术学习
专业技术学习
搜搜题库系统