C-查找数组组合以使用最少数量的数组覆盖所有元素

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＆amp;D或B＆amp;c因此答案将是两个数组。

不必用1填充，可以是2或3或其他。只需要剩下零。由于我们只在搜索最低数字，因此可能有多种组合，但只有一个答案。L将小于10。阵列数量将从1到500不等。

我尝试使用在线学习的图形算法，但是这个问题使我感到困惑。

Answer 1

我已经使用divide＆amp;征服方法。
逻辑
首先，考虑阵列的集合data，我们想从中找到最小的数组，其中的组合仅为1。



简而言之从其余阵列中找到最小的组，以便组中阵列的组合＆amp;当前阵列满足条件。＆amp;最小的组合(阵列 当前数组(是我们的解决方案。

我们可以简单地给出问题的递归定义。

解决方案

#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跟踪我们在实例中找到的最佳解决方案。