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

Question

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

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

这是我的解决方案(所有出现的 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，引导一个人(用更长的时间)通过，与一个人一起返回并递归剩下的人。不幸的是它不起作用 - 输入 {1,2,5,10}它应该返回 17，但我的函数输出 19。

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

Answer 1

问题是你没有考虑到一个已经留在对岸的人将来可以拿着手电筒回来。在这个例子中，2 号人在一段时间后返回。基本上不是第 i,j 对中的一个人会带着手电筒返回。