我的回溯代码中的错误 - Bridge Crossing

Question

我正在尝试学习回溯，为此我选择了一个 TopCoder 问题 - 它称为 BridgeCrossing。我们有 1-6 个人试图在晚上过桥，他们之间有一个手电筒。一次最多2个人可以过桥，过桥时，至少其中一个人必须有手电筒，否则他们什么也看不到...

答案是一个给定 vector <int> times 的函数，其中 times[i-1] 表示第 i 个人过桥所需的时间（当 2 个人过桥时，他们的时间是第来自较慢的人）。另外，当我们在桥的另一边有手电筒时，还有一些人需要过桥 - 一个人必须 return 拿着手电筒才能引导他们通过。

这是我的解决方案（vector <int> 的所有出现都变成了 VI）：

int backtrack(VI times){
        if (times.empty()) return 0;
        if (times.size() == 1) return times[0];
        if (times.size() == 2) return max(times[0], times[1]);
        VI results;
        for (int i = 0; i < times.size(); i++){
            for (int j = 0; j < i; j++){
                VI people_left1;
                for (int k = 0; k < times.size(); k++){
                    if (k != i && k != j){
                        people_left1.push_back(times[k]);
                    }
                }
                people_left1.push_back(min(times[i], times[j]));
                results.push_back(backtrack(people_left1)+
                max(times[i], times[j]) + min(times[i], times[j]));
            }
            for (int j= i + 1; j < times.size(); j++){
                VI people_left;
                for (int k = 0; k < times.size(); k++){
                    if (k != i && k != j){
                        people_left.push_back(times[k]);
                    }
                }
                people_left.push_back(min(times[i], times[j]));
                results.push_back(backtrack(people_left)+
                max(times[i], times[j]) + min(times[i], times[j]));
            }
        }
        int res = INT_MAX;
        for (int i = 0; i < results.size(); i++){
            if (results[i] < res){
                res = results[i];
            }
        }
        return res;
    }

理论上它应该运作良好 - 我正在选择所有可能的索引对 i，j，引导一个人（用更长的时间）通过，return 与一个人一起并在剩下的人身上递归。不幸的是它不起作用 - 对于输入 {1,2,5,10} 它应该 return 17，但我的函数输出 19.

我已经盯着这段代码看了很长时间了，但我仍然看不到任何错误。一个人可能藏在哪里？另外，调试此类递归函数的技术是什么，因为我在很长一段时间内一直遇到问题。

Answer 1

不是真正的答案，但这样做可以使您的代码更具可读性：

for (int j = 0; j < times.size(); j++){
    if (j != i) {
    .. all that code inside both loops               
    }
}

也许这样可以更容易地找到您的问题。

有时，您可以通过根据递归级别缩进打印信息来调试递归代码。为此，您必须添加一个向下传递到每个级别的变量。当你调低一个级别时增加它。

method(int level, ...) {
    if (recursing needed) {
         print(spaces(level * 3) + "recursing");
         method(level + 1);
    }
}

Answer 2

问题是你没有考虑到一个已经留在另一边的人以后可以return拿着手电筒。在示例中，一段时间后人数为 2 returns。基本上不是第 i,j 对的人都会 return 用手电筒。

我的回溯代码中的错误 - Bridge Crossing

Bug in my backtracking code - Bridge Crossing

c++

algorithm

backtracking