0

作为家庭作业的一部分，我需要编写一个函数，如果给定的数组中存在“好”子组，则返回 true。“好子组”是每个组成员中特定字段（整数）的总和大于给定目标（特别是数组原始长度的一半）的子组，并且每个组成员小组与小组的所有其他成员“相处”。如果 2 个成员“相处融洽” (abs(m1->f1 - m2->f1) + abs(m1->f2 - m2-f2)) <= given_hatred。这是我到目前为止尝试过的，但似乎不起作用：

//-----helpers-----

//checks if the new candiate member likes the others
static bool fits(Member* a,int curr,int chosen[],double get_along)
{
    for(int i=0; i<curr;i++)
    {
        if(chosen[i]==1)
        {
            int iA=memberGetGAFactorA(a[i]);
            int iB=memberGetGAFactorB(a[i]);
            int currA=memberGetGAFactorA(a[curr]);
            int currB=memberGetGAFactorB(a[curr]);

            if(abs_f(iA-currA)+abs_f(iB-currB)>get_along)
                return false;
        }
    }

    return true;
}

//backtracking
static bool subsum(Members* a, int n, int size, int sum, int chosen[], int curr, double get_allong)
{
    if(sum > size)
        return true;

    if(n <= 0)
        return false;

    if(fits(arr,curr,chosen,get_along))
    {
        chosen[curr]=1;
        int inSum = sum+memberGetFieldNum(a[0]);
        if (subsum(a+1, n-1, size - memberGetFieldNum(a[0]), inSum, chosen, curr + 1, get_along))
            return true;
    }

    chosen [curr] = 0;      
    return subsum(a+1,n-1,size,sum,chosen,curr+1,get_along);
}

//------the wanted function-------
bool subGroupExists(Members* array,length, double get_along)
{
    int* chosen = calloc(length,sizeof(int));
    bool res = subsum(array,length,length/2,0,chosen,0,get_along);

    free(chosen);
    return res;
}

我还要提到 Member 是一种抽象数据类型，它实现了所有以开头的函数，member....并且工作正常（经过测试）。

编辑： 我找到了一个解决方法，我很快就会发布，但我对其他解决方案非常感兴趣，所以请随意:)

4

0 回答 0