我的回溯函数有问题,它会循环某些数据,我不能在这里写整个程序代码,但可以把我的函数放在这里。
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
中
的
元素
数指数组值
该函数获取长度为 values 数组的元素的数量,values 一个包含数字的数组,从最高到最低排序,索引控制递归,默认为 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 周,并询问了我所有的朋友,但没有人知道它有什么问题。我知道这与背包问题有点关系,但我还没有那个问题,仍然需要学习。
我期待任何可以提供帮助的答案。
我很抱歉我的标点符号,但我是第一次来这里,不习惯格式化。
这里有一个例子:
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;}