查找陣列組合以覆蓋使用最少數量陣列的所有元素

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。

對於上面的示例，它將是A & D或B & C，因此答案將是兩個數組。

它不必填寫1，它可以是2或3或其他。只需要不剩零。由於我們只搜索最小號碼，因此可能有多個組合，但只有一個答案。 L會小於10.但是陣列數量從1到500不等。

我試過使用圖形算法，我在網上學到的，但這個問題讓我難堪。

Answer 1

我已經用拆分&征服的方法解決了這個問題。
邏輯
首先考慮我們想要找到最小的組數組的數組data的收集，組合，其中只有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跟蹤我們的實例已經找到最佳的解決方案。