c++ - 递归回溯

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 - 引用数组值的 bool 元素数组

该函数获取元素的数量，它是 values 数组的长度，values 是一个包含数字的数组，从最高到最低排序，index 控制递归，默认为 0，因此它从第一个元素 moneyA 变量开始存储值数组中的数字，它应该达到一半，即从值数组中求和的数字的一半，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 周，并询问了我所有的 friend ，但没有人知道它出了什么问题。我知道这与背包问题有点关系，但我还没有那个，仍然需要学习。

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

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

举个例子:

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

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

编辑:让我们从简化蛮力算法开始:

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

执行后，solution包含一个用于达到目标的值的列表，返回的指针指示列表的结尾。

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

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

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

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