递归回溯

Question

我的回溯函数有问题，它会循环某些数据，我无法在这里编写整个程序代码，但可以将我的函数放在这里。

bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen)
{

    if(moneyA == half)
        return true;
    else if(index >= quantity)
        return false;

    moneyA += values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = true;
        return true;
    };

    moneyA -= values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = false;
        return true;
    };

    return false;
}

现在解释一下：

数量 - 值数组中的元素数量
值 - 数字数组
index - 控制递归的变量
MoneyA - 存储数组值中元素总和的变量
half - 递归完成后 MoneyA 应该达到的数字
ifChosen - 引用数组值的布尔元素数组

该函数获取元素的数量，即值数组的长度，值是一个数组，其中的数字从最高到最低排序，索引控制递归，默认为 0，因此它开始从第一个元素开始，money 是一个变量，用于存储值数组中的数字，它应该达到一半，即从值数组中求和的数字的一半，而 ifChosen 存储所选的数字。

整个函数就是这样做的，它对values数组中的元素进行求和，并检查它是否达到了一半，如果它低于一半，则将其添加到moneyA并在ifChosen中标记它，然后它会转到下一个，如果总和高于它的一半返回并在 ifChosen 数组中取消标记并从 MoneyA 中减去。它应该始终获得最高的元素。

这是一个简单的例子：

6 - number of elements
50, 20, 19, 15, 2, 2 - elements stored in values array
total sum is - 108
half of elements - 54

这个结果应该是：

50, 2, 2 - marked as true in ifChosen
20, 19, 15 - marked as false in ifChosen 

当然，对于这个简单的例子来说，它做得很好，但对于具有更多数字且一个数字出现多次的更复杂的例子，它会循环并且递归永远不会停止。我实际上已经为此工作了 1.5 周，并询问了我所有的朋友，但没有人知道它出了什么问题。我知道这与背包问题有一点关系，但我还没有那个，仍然需要学习。

我期待任何有帮助的答案。

我很抱歉我的标点符号，但我是第一次来这里，不习惯格式。

这里有一个例子：

89 86 83 67 53 45 5 1    

44 43 34 33 33 24 23 23 23 22 21 21 19 12 11 9 8 7 5 3 2 2 2 1 1 1 1 1     

real    0m28.007s    

user    0m27.926s    

sys 0m0.028s

现在我认为它会永远循环： 43 个元素：

12 2 2 1 3 4 5 6 7 89 33 12 45 23 44 23 11 44 1 3 5 7 88 33 8 19 43 22 86 5 34 23 21 67 83 24 21 53 9 11 34 1 1

@Karl Bielefeldt 是的，我知道有很多组合，这就是我试图加快速度的原因。现在这就是我得到的全部，但对于某些输入它给了我错误的结果。任何人都可以纠正它，它的工作速度比以前快得多吗？

bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen){

if(index>=quantity && moneyA == half){ return true;}
else if(index>=quantity) return false;

moneyA+=values[index];
ifChosen[index]=true;

if(moneyA<=half){       
    shareMoney(quantity,values,index+1,moneyA, half,ifChosen);
    if(moneyA==half) return true;

    return true;
}else{
    shareMoney(quantity,values,index+1,moneyA, half,ifChosen);      
    moneyA-=values[index];
    ifChosen[index]=false;

    return true;
}


return false;}

Answer 1

减少此类问题迭代次数的典型方法是通过求解线性程序来计算子树上的界限（就像您的问题一样，但其余变量允许采用小数值）。单纯形法以近似二次方的时间而不是指数的时间求解线性程序。线性程序的最佳解决方案至少与具有相同约束的最佳整数或二进制解决方案一样好，因此，如果线性解决方案比当前最佳解决方案更差，您可以丢弃整个子树而不进行详尽的评估。

编辑：让我们从简化暴力算法开始：

int* shareMoney( int pool_size, int *pool, int *solution, int cumsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    int max = cumsum;
    for( int n = pool_size; n--; max += pool[n] );
    if (max < goal) return 0;
#endif

    int* subproblem = shareMoney(pool_size-1, pool+1, solution, cumsum, goal);
    if (subproblem) return subproblem;

    *solution = *pool;
    return shareMoney(pool_size-1, pool+1, solution+1, cumsum+*pool, goal);
}

执行后，解决方案包含用于达到目标的值的列表，返回的指针指示列表的末尾。

条件块是我建议的第一个改进。在这些情况下不需要递归。

我们可以消除在每一步迭代计算最大值的需要：

int* shareMoney( int pool_size, int *pool, int *solution, int cumsum, int poolsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    if (cumsum + poolsum < goal) return 0;
#endif

    int* subproblem = shareMoney(pool_size-1, pool+1, solution, cumsum, poolsum - *pool, goal);
    if (subproblem) return subproblem;

    *solution = *pool;
    return shareMoney(pool_size-1, pool+1, solution+1, cumsum+*pool, poolsum - *pool, goal);
}

这是一个解决整数版本的函数（对于重复的硬币面额更好）：

int* shareMoney( int pool_size, int *pool_denom, int *pool_cardinality, int *solution, int cumsum, int poolsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    if (cumsum + poolsum < goal) return 0;
#endif

    poolsum -= *pool_cardinality * *pool_denom;
    for (*solution = *pool_cardinality; *solution >= 0; --*solution) {
        int* subproblem = shareMoney(pool_size-1, pool_denom+1, pool_cardinality+1, solution+1, cumsum + *solution * *pool_denom, poolsum, goal);
        if (subproblem) return subproblem;
    }

    return 0;
}

它不需要获得单个硬币的直接列表，而是需要一个面额列表和数量每个可用硬币的数量。结果是解决方案所需的每种面额的硬币数量。

Answer 2

对于 43 个元素，有接近 9 万亿种可能的组合。如果您必须检查全部 9 万亿，则没有办法加快速度，但如果您不想等那么久，诀窍是尝试将答案放在更接近循环开始的位置。我认为您可能已经通过按升序对它进行排序找到了正确的解决方案。这可能会更快，因为它首先排列大块（因为您正在进行深度优先递归）。

如果我正确理解这个问题，就会找到最小元素的组合，加起来恰好是总值的一半。这意味着未选择的元素也加起来应该恰好是总值的一半，并且将是最大的元素。