gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:56:46 25 4
gpt4 key购买 nike

您好,我是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 不等。

我已经尝试使用我在网上学到的图算法,但这个问题让我很困惑。

最佳答案

我已经使用分而治之方法解决了这个问题。
逻辑
首先,考虑数组 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 来跟踪我们在实例中找到的最佳解决方案。

关于c - 使用最少的数组查找数组组合以覆盖所有元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44319786/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com