marriage.java

稳定婚姻：第一步配成一对夫妇, 即组成一个有序对, 以此作为问题的部分解, 以后每一步考虑一男一女, 如果将他们组成有序对并加入到部分解中, 不会引起不稳定, 则加入之 否则, 不组成有序对, 而是考

/**
 *
 */
import java.lang.*;
public class Marriage
{	
    private	int mr[][]={{7,2,6,5,1,3,8,4},
				 		{4,3,2,6,8,1,7,5},
						{3,2,4,1,8,5,7,6},
						{3,8,4,2,5,6,7,1},
						{8,3,4,5,6,1,7,2},
						{8,7,5,2,4,3,1,6},
						{2,4,6,3,1,7,5,8},
						{6,1,4,2,7,5,3,8}};
					 
	private	int wr[][]={{4,6,2,5,8,1,3,7},
						{8,5,3,1,6,7,4,2},
						{6,8,1,2,3,4,7,5},
						{3,2,4,7,6,8,5,1},
						{6,3,1,4,5,7,2,8},
						{2,1,3,8,7,4,6,5},
						{3,5,7,2,4,1,8,6},
						{7,2,8,4,5,6,3,1}};
					
	private	int[][] mw=new int[mr.length][mr.length];
	private	int[][] wm=new int[mr.length][mr.length];
	private	int[] x=new int[mr.length]; 
	private	int[] y=new int[mr.length];
	private	int[] min=new int[mr.length];
	private int mina=162;
	private	boolean[] single=new boolean[mr.length];
	private	boolean q;
	
	public Marriage()
	{ 
	  for (int i=0;i<mr.length;i++)
  		{for (int j=0;j<mr.length;j++)
  			{
	         mw[i][mr[i][j]-1]=j+1;
	         wm[i][wr[i][j]-1]=j+1;
            }
          single[i]=true;
        }
	
	}
	
	public void tryIt(int m,boolean q)
    {
	  boolean s=false;   
      int r,w; 
	      r=-1;		
      do
	  {	
    	r++;
        w=mr[m][r]-1;
    	if (single[w]&&check(m,r))
		{
			x[m]=w+1;
			y[w]=m+1;
			single[w]=false;
			if (m<mr.length-1) 
			{
				tryIt(m+1,s);
			//	if (!S)single[w]=true;
			}
			else  printMarriage(x);	
		single[w]=true;
		}
   	  }while(r<mr.length-1);
      q=s;
    }

    public boolean check(int n,int wn)
    {
      int i,l,pw,pm,w;
	  boolean s;
	  s=true;
	  i=0;
	  l=0;
	  w=mr[n][wn]-1;
	  
      while((i<wn)&&s)
      {
		pw=mr[n][i]-1;
        i++;
        if(!single [pw])
        s=wm[pw][n]>wm[pw][y[pw]-1];
      } 
      
	  i=0;
      l=wm[w][n]-1;
      
	  while((i<l)&&s)
      {
		pm=wr[w][i]-1;
        i++;
       if(pm<n)   
		   s=mw[pm][w]>mw[pm][x[pm]-1];
      }
       
	  return s;
     }
     
     public void printMarriage(int A[])
     {
       int m, rm, rw;
       rm = 0; rw = 0;
       for( m=0; m<mr.length; m++)
       { 
	     System.out.print("("+(m+1)+" "+A[m]+"), ");
         rm += mw[m][A[m]-1];
         rw += wm[A[m]-1][m];
       }
       System.out.println("");
       System.out.print("男女双方满意的程度及总体满意程度:");
       System.out.println(rm+", "+rw+", "+(rm+rw));	
       //System.out.println("");
       if ((rm+rw)<mina)
       {
	     for (m=0;m<mr.length;m++)
		   min[m]=A[m];
	       mina=rm+rw;
       }

     }
     
        
	public static void main(String[] args)
	{
               boolean p=false;
               Marriage test=new Marriage();
	   System.out.println("配对婚姻情况如下:");
               test.tryIt(0,p);
               System.out.println("总体满意程度最好为:");
               test.printMarriage(test.min);	
	}
	
}