回溯法解部落冲突问题

部落冲突问题：原始部落byteland中的居民们为了争抢有限的资源，经常发生冲突。几乎每个居民都有它的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。

算法设计：给定byteland部落中居民间的仇敌关系，计算组成部落卫队的最佳方案。

数据输入：首先输入两个正整数n个m，表示byteland部落中有n个居民，居民间有m个仇敌关系。居民编号为1,2,…,n。接下来输入m对正整数，每对正整数包含u和v，表示居民u和居民v是仇敌。

结果输出：首先输出部落卫队最佳组建方案中包含的居民人数。之后逐个输出卫队组成xi, 1<=xi<=n, xi=0表示居民i不在卫队中，xi=1表示居民i在卫队中。

package 部落冲突;

public class Backtrack
{
    static int[] x;//当前子集
    static int n;//二叉树层数，即部落总人数
    static int cn;//当前队伍人数
    static int bestn;//最大队伍人数
    static int[] bestx;//最优解
    static int[][] a;//表示队伍人员关系的邻接矩阵
    /**回溯法解最大团算法（部落冲突问题）
     * @param i   当前层数
     */
    public static void backTrack(int i){
        if(i>n){
            for(int b=1;b<=n;b++){
                bestx[b]=x[b];
                
                
            }
            bestn=cn;
            return;
        }
        boolean ok=true;//临界条件：与任一已入选护卫队的队员无仇
        for(int j=1;j<i;j++){
            if(x[j]==1&&a[i][j]==1){
                ok=false;
                break;
            }
        }
        if(ok){
            x[i]=1;
            cn++;
            backTrack(i+1);
            cn--;
        }
        if((cn+(n-i))>bestn){
            x[i]=0;
            backTrack(i+1);
        }
    }
    public static void main(String[] args)
    {
        int[] c1={10,1,2,3,4,5,6,7,8,8,9};//初始化仇人
        int[] c2={1,5,3,5,6,8,7,8,9,10,10};//同上
        n=10;
        cn=0;
        bestn=0;
        bestx=new int[n+1];
        x=new int[n+1];
        a=new int[n+1][n+1];
        for(int h1=1;h1<a.length;h1++){
            a[0][h1]=h1;
            a[h1][0]=h1;
        }
        for(int h1=0;h1<c1.length;h1++){//构建邻接矩阵
            a[c1[h1]][c2[h1]]=1;
            a[c2[h1]][c1[h1]]=1;
        }

        System.out.println("敌对关系：");
        for(int h1=0;h1<c1.length;h1++){
            System.out.print(c1[h1]+" vs "+c2[h1]);
            System.out.println();
        }
        backTrack(1);
        System.out.println("队伍最大人数达: "+bestn);
        System.out.print("分别是：");
        for(int h4=1;h4<bestx.length;h4++){
            if(bestx[h4]==1){
                System.out.print(h4+" ");
            }
        }
    }
    

}