最小配列数を使用してすべての要素をカバーする配列の組み合わせを見つける

Question

こんにちは私はCを学ぶのが初めてで、さまざまな問題を解決しようとしています。問題の私の最近の試みは半分解決されています。最後のステップについて私が知る必要があるのはこれです。

int A[4] = {1,0,1,0}; 
int B[4] = {1,0,0,1}; 
int C[4] = {0,1,1,0}; 
int D[4] = {0,1,0,1}; 

そして、すべての配列は同じ長さ 'L'です。私は結合したとき（同じ位置にあるすべての要素が、最初はゼロで埋められた等しい長さの配列に追加されます）、配列の長さがLである配列につながる配列の最小量を使用する組み合わせを理解する必要があります'それには0が1つもありません。

上記の例では、A & DまたはB & Cのいずれかになります。したがって、答えは2つの配列になります。

1を入力する必要はありません.2または3などとすることができます。残されたゼロはない必要があります。私たちは最小数だけを探しているので、複数の組み合わせがあるかもしれませんが、ただ1つの答えです。 Lは10より小さくなります。配列の数は1から500まで変化します。

私はオンラインで学んだグラフアルゴリズムを使用しようとしましたが、この問題は私には面倒です。

Answer 1

私はこの問題をの除算&の征服者を使用して解決しました。
論理
まず最初に配列の集合を考えてみましょう。この配列から最小の配列グループを探したいと思います。その組み合わせは1だけの配列です。

&グループ内のすべての配列を、残りの配列から最も小さいグループを見つけて、グループ&の配列の組み合わせが条件を満たすようにするだけです。 &最小の組み合わせ（配列のグループ+現在の配列）は私たちの解決策です。

問題の再帰的な定義を単純に与えることができます。ここ

ソリューション

#include<stdio.h> 
#define L 4 //length of the array 
#define N 4 //number of arrays 
int best[N]; //array to keep track of best combination. 
int nbest=N; //number of best arrays in best combination. 
int D[N][L]={{1,0,1,0},{1,0,0,1},{0,1,1,0},{0,1,0,1}}; //data 
int func(int track[],int ar[],int d); //get best combination 
int * copy(int *a,int len); //copy contant of a to b. 
int * combine(int a[],int b[],int len); 
int main() 
{ 
    int i,j; 
    int empty[L]={0,0,0,0};//initial combination 
    int init[N]={-1,-1,-1,-1};//initial track. 
    // initialize 'best' array. 
    for(i=0;i<N;i++) 
     best[i]=-1; 
    // initial function call 
    func(init,empty,0); 
    // print the result. 
    printf("best combination..\n"); 
    for(i=0;i<nbest;i++){ 
     for(j=0;j<L;j++) 
      printf("%d, ",D[best[i]][j]); 
     printf("\n"); 
    } 
    return 0; 
} 

/* 
    * this is recursive function work on data array 'D'. 
    * array 'track' is used to keep track of the arrays of current combination. 
    * array 'ar' is indicate the current combination. 
    * int 'd' indicate the number of arrays in current combination. 
*/ 
int func(int track[],int ar[],int d){ 
    int i,j,*t,*tr; 
    if(d>=N) //check if there are arrays remain to combine. 
     return 0; 
    if(check(ar,L)){ //check if the combination is valid. 
     if(nbest>d){ //check if the current solution is better then the best. 
      nbest=d; 
      for(i=0;i<d;i++) 
       best[i]=track[i]; 
     } 
     return 1; 
    } 
    tr=copy(track,N); //make local copy of track. 
    for(i=0;i<N;i++){ // make combination with all remaining arrays. 
     if(isin(tr,i)) // check if current array is already in combination. 
      continue; 
     t=copy(ar,L); //make local copy of current combination. 
     tr[d]=i; // update track array to track current array. 
     t=combine(t,D[i],L); // combine the array with current combination. 
     if(func(tr,t,d+1)){ // recursive call, brake the loop if the current combination is valid. 
      break; 
     } 
    } 
    return 0; 
} 

int * combine(int a[],int b[],int len){ // return combination of array 'a' & 'b'. 
    int *c=(int *)calloc(len,sizeof(int)); 
    int i; 
    for(i=0;i<len;i++){ 
     c[i]=a[i]||b[i]; 
    } 
    return c; 
} 

int * copy(int *a,int len){ // this function return copy of array 'a' of length 'len' 
    int i; 
    int *t=(int *)calloc(len,sizeof(int)); 
    for(i=0;i<len;i++) 
     t[i]=a[i]; 
    return t; 
} 

int check(int a[],int len){ // check if the array is valid combination. i.e. all elememnts are 1. 
    int i; 
    for(i=0;i<len;i++) 
     if(a[i]!=1) 
      return 0; 
    return 1; 
} 

int isin(int *ar,int index){ // return 1 if int 'index' is exist in array 'ar'. 
    int i; 
    for(i=0;i<N;i++) 
     if(ar[i]==index) 
      return 1; 
    return 0; 
} 

私たちは、インスタンスで発見した最高のソリューションを追跡するために、配列bestを使用していました。