递归回溯

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

现在这里是解释:

quantity - values中的元素数量数组
值 - 数字数组
index - 用于控制递归的
变量moneyA - 存储元素之和的变量,数组值的
一半 - moneyA在递归完成后应该达到的数字
ifChosen - 布尔元素的数组指数组值

该函数获取值为数组的元素数量,值为一个数组,其中数字从最高到最低排序,索引控制递归,默认为0,因此它从第一个元素moneyA变量开始,该变量存储来自values数组,它应该达到一半,这是从数值数组中取出的数字的一半,ifChosen存储了所选择的数字.

整个函数执行此操作,它将值数组中的元素相加并检查它是否达到了一半,如果它低于一半将其添加到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

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

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