Finding array combination to cover all elements using least amount of arrays

Question

Hello I am new to learning C and have been trying to solve various problems. My latest attempt at a problem is half solved, what I need to know for the final step is this. If there are various arrays like such :

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};

And all the arrays are the same length 'L'. I need to figure out the combination that uses the least amount of arrays that when combined(all the elements in the same position is added to an array of equal length that is initially filled with zeros), will lead to an array of length 'L' that doesn't have a single 0 in it.

For the example above, it will be either A & D, or B & C thus the answer will be two arrays.

It doesn't have to be filled with 1s, it can be 2 or 3 or whatever. There just needs to be no zeros left. Since we are only searching for the minimum number, there may be multiple combinations, but only one answer. L would be smaller than 10. The number of arrays will vary from 1 to 500 though.

I've tried using graph algorithms I learned online, but this problem has me stumped.

Answer 1

I have solved this problem using Divide & Conquer approach.
Logic
first of all, consider collection of arrays data from which we want to find smallest group of arrays, combination of which is array of only 1's.

simply we can take all the array from collection one by one & find smallest group from the remaining arrays such that the combination of the arrays in the group & current array is satisfy the condition. & the smallest combination (group of array + the current array) is our solution.

we can simply give the recursive definition of the problem.

solution

#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;
}

here I have used array best to keep track of best solution we have found at instance.