彩票N保M缩水问题（最小集合覆盖问题）

#include <stdio.h>

#include <string.h>

#include <time.h>

#include <stdlib.h>

#include <windows.h>



char s[243][6]={

"33333", "33331", "33330", "33313", "33311", "33310", "33303", "33301", 

"33300", "33133", "33131", "33130", "33113", "33111", "33110", "33103", 

"33101", "33100", "33033", "33031", "33030", "33013", "33011", "33010", 

"33003", "33001", "33000", "31333", "31331", "31330", "31313", "31311", 

"31310", "31303", "31301", "31300", "31133", "31131", "31130", "31113", 

"31111", "31110", "31103", "31101", "31100", "31033", "31031", "31030", 

"31013", "31011", "31010", "31003", "31001", "31000", "30333", "30331", 

"30330", "30313", "30311", "30310", "30303", "30301", "30300", "30133", 

"30131", "30130", "30113", "30111", "30110", "30103", "30101", "30100", 

"30033", "30031", "30030", "30013", "30011", "30010", "30003", "30001", 

"30000", "13333", "13331", "13330", "13313", "13311", "13310", "13303", 

"13301", "13300", "13133", "13131", "13130", "13113", "13111", "13110", 

"13103", "13101", "13100", "13033", "13031", "13030", "13013", "13011", 

"13010", "13003", "13001", "13000", "11333", "11331", "11330", "11313", 

"11311", "11310", "11303", "11301", "11300", "11133", "11131", "11130", 

"11113", "11111", "11110", "11103", "11101", "11100", "11033", "11031", 

"11030", "11013", "11011", "11010", "11003", "11001", "11000", "10333", 

"10331", "10330", "10313", "10311", "10310", "10303", "10301", "10300", 

"10133", "10131", "10130", "10113", "10111", "10110", "10103", "10101", 

"10100", "10033", "10031", "10030", "10013", "10011", "10010", "10003", 

"10001", "10000", "03333", "03331", "03330", "03313", "03311", "03310", 

"03303", "03301", "03300", "03133", "03131", "03130", "03113", "03111", 

"03110", "03103", "03101", "03100", "03033", "03031", "03030", "03013", 

"03011", "03010", "03003", "03001", "03000", "01333", "01331", "01330", 

"01313", "01311", "01310", "01303", "01301", "01300", "01133", "01131", 

"01130", "01113", "01111", "01110", "01103", "01101", "01100", "01033", 

"01031", "01030", "01013", "01011", "01010", "01003", "01001", "01000", 

"00333", "00331", "00330", "00313", "00311", "00310", "00303", "00301", 

"00300", "00133", "00131", "00130", "00113", "00111", "00110", "00103", 

"00101", "00100", "00033", "00031", "00030", "00013", "00011", "00010", 

"00003", "00001", "00000"};



struct map{

    unsigned a1;

    unsigned a2;

    unsigned a3;

    unsigned a4;

    unsigned a5;

    unsigned a6;

    unsigned a7;

    unsigned a8;

};



int mycheck(char *a,char *b){

    int cnt=0;

    int i;

    for(i=0;i<5;i++){

        if(a[i]==b[i]) cnt++;

    }

    if(cnt>=3) return 1;

    else return 0;

}



int isfull(struct map *a){

	if((a->a1==4294967295)&&(a->a2==4294967295)&&(a->a3==4294967295)&&(a->a4==4294967295)

		&&(a->a5==4294967295)&&(a->a6==4294967295)&&(a->a7==4294967295)&&(a->a8==524287)) return 1;

	return 0;

}



void mergem(struct map *a,struct map *b){

	a->a1|=b->a1;

	a->a2|=b->a2;

	a->a3|=b->a3;

	a->a4|=b->a4;

	a->a5|=b->a5;

	a->a6|=b->a6;

	a->a7|=b->a7;

	a->a8|=b->a8;

}



void myprint(int *p,int n){

    int i;

	char rl[243];

	memset(rl,0,sizeof(rl));

	printf("find |T|=%d answer:\n",n);

    for(i=0;i<n;i++){

		rl[p[i]]=1;

    }

	for(i=0;i<243;i++){

		if(rl[i]==1) printf("\"%s\", ",s[i]);

	}

    printf("\n");

}



int dif(struct map *a,struct map *b){

    int cnt=0;

    int i;

    for(i=0;i<32;i++){

        if(((a->a1&(1<<i))==0)&&((b->a1&(1<<i))!=0)) cnt++;

    }

    for(i=0;i<32;i++){

        if(((a->a2&(1<<i))==0)&&((b->a2&(1<<i))!=0)) cnt++;

    }

    for(i=0;i<32;i++){

        if(((a->a3&(1<<i))==0)&&((b->a3&(1<<i))!=0)) cnt++;

    }

    for(i=0;i<32;i++){

        if(((a->a4&(1<<i))==0)&&((b->a4&(1<<i))!=0)) cnt++;

    }

    for(i=0;i<32;i++){

        if(((a->a5&(1<<i))==0)&&((b->a5&(1<<i))!=0)) cnt++;

    }

    for(i=0;i<32;i++){

        if(((a->a6&(1<<i))==0)&&((b->a6&(1<<i))!=0)) cnt++;

    }

    for(i=0;i<32;i++){

        if(((a->a7&(1<<i))==0)&&((b->a7&(1<<i))!=0)) cnt++;

    }

    for(i=0;i<32;i++){

        if(((a->a8&(1<<i))==0)&&((b->a8&(1<<i))!=0)) cnt++;

    }

    return cnt;

}



int ruler[243]={0};



void myrand(int *rd){

	int i,r;

	for(i=0;i<7;i++) r=(int)(10.0*rand()/(RAND_MAX+1.0));

	rd[0]=(int)(32.0*rand()/(RAND_MAX+1.0));

	rd[1]=32+(int)(32.0*rand()/(RAND_MAX+1.0));

	rd[2]=64+(int)(32.0*rand()/(RAND_MAX+1.0));

	rd[3]=96+(int)(32.0*rand()/(RAND_MAX+1.0));

	rd[4]=128+(int)(32.0*rand()/(RAND_MAX+1.0));

	rd[5]=160+(int)(32.0*rand()/(RAND_MAX+1.0));

	rd[6]=192+(int)(31.0*rand()/(RAND_MAX+1.0));

	rd[7]=214+(int)(30.0*rand()/(RAND_MAX+1.0));

}



int main(){

    int i,j;

    struct map m[243];

    struct map mp,mp2;

	int p[9]={0};

	int tt=0;

	int ll[8]={0};

	int pp[8]={0};

	srand((int)time(0));



	/*create map*/

    memset(m,0,sizeof(m));

    for(i=0;i<243;i++){

        for(j=0;j<32;j++){

            if(mycheck(s[i],s[j])) m[i].a1|=(1<<j);

        }

        for(j=32;j<64;j++){

            if(mycheck(s[i],s[j])) m[i].a2|=(1<<(j-32));

        }

        for(j=64;j<96;j++){

            if(mycheck(s[i],s[j])) m[i].a3|=(1<<(j-64));

        }

        for(j=96;j<128;j++){

            if(mycheck(s[i],s[j])) m[i].a4|=(1<<(j-96));

        }

        for(j=128;j<160;j++){

            if(mycheck(s[i],s[j])) m[i].a5|=(1<<(j-128));

        }

        for(j=160;j<192;j++){

            if(mycheck(s[i],s[j])) m[i].a6|=(1<<(j-160));

        }

        for(j=192;j<224;j++){

            if(mycheck(s[i],s[j])) m[i].a7|=(1<<(j-192));

        }

        for(j=224;j<243;j++){

            if(mycheck(s[i],s[j])) m[i].a8|=(1<<(j-224));

        }

    }



	/*create rand*/

	myrand(ll);

	printf("rand map: ");

	for(i=0;i<8;i++) printf("%d, ",ll[i]);

	printf("\n");



	for(pp[0]=0;pp[0]<8;pp[0]++){

	for(pp[1]=pp[0]+1;pp[1]<8;pp[1]++){

	for(pp[2]=pp[1]+1;pp[2]<8;pp[2]++){

	for(pp[3]=pp[2]+1;pp[3]<8;pp[3]++){



	p[0]=ll[pp[0]];p[1]=ll[pp[1]];p[2]=ll[pp[2]];p[3]=ll[pp[3]];

	printf("[%2d/70] test: %3d,%3d,%3d,%3d,...\n",++tt,p[0],p[1],p[2],p[3]);//prt

			for(p[4]=0;p[4]<243;p[4]++){

			if(p[4]==p[3]||p[4]==p[2]||p[4]==p[1]||p[4]==p[0]) continue;

		for(p[5]=0;p[5]<243;p[5]++){

			if(p[5]==p[4]||p[5]==p[3]||p[5]==p[2]||p[5]==p[1]||p[5]==p[0]) continue;

			if(p[5]<p[4]) continue;

		for(p[6]=0;p[6]<243;p[6]++){

			if(p[6]==p[5]||p[6]==p[4]||p[6]==p[3]||p[6]==p[2]||p[6]==p[1]||p[6]==p[0]) continue;

			if(p[6]<p[5]) continue;

			memset((char*)&mp2,0,sizeof(mp2));

			for(i=0;i<7;i++) mergem(&mp2,&m[p[i]]);

			if(isfull(&mp2)){

				myprint(p,7);

			}

		for(p[7]=0;p[7]<243;p[7]++){

			if(p[7]==p[6]||p[7]==p[5]||p[7]==p[4]||p[7]==p[3]||p[7]==p[2]||p[7]==p[1]||p[7]==p[0]) continue;

			if(p[7]<p[6]) continue;

			memset((char*)&mp,0,sizeof(mp));

			mergem(&mp,&mp2);

			mergem(&mp,&m[p[7]]);

			if(isfull(&mp)){

				myprint(p,8);

			}

		}//7

		}//6

		}//5

		}//4

		}//3

		}//2

		}//1

	}//0

    return 0;

}