关于剪枝有个问题

Question

关于剪枝有个小问题，这里为啥不能直接使用上一个进行比较？ 必须要定一个变量，没有特别明白

  if (prei > -1 && stick[i] == stick[prei])
                continue;
            prei = i;
   marked[i] = true;
   dfs(k, l + stick[i], i);
   marked[i] = false;

Answer 1

吉他熊 2022-06-27 10:42:02

哈哈我一直期待有人问这个问题来着 :)

原因也简单，因为stick[i - 1]很有可能在拼前一个长木棍的时候被用掉了，所以即便stick[i] = stick[i - 1]，但是stick[i]却是剩下的同等长度的小木棍里的第一个，这个时候就不能跳过它了

比方说这种情况，当前枚举到的长木棍长度为8

stick:  5 4 3 3 2 1

marked: T F T F F F

这轮搜索的时候第一个循环到4，然后prei = 1，之后第二个可用的是第二个3（注意第一个3之前拼别的长木棍用掉了），这时stick[i] == 3，跟stick[prei] == 4不一样，所以这个3是可以继续搜索的。如果直接和stick[i - 1]比较，发现都是3，会误判为没必要搜索，就出错了

我这里的处理方法是记录这一层的上一轮用的哪根小木棍，不过其实也有别的处理方法，比如结合marked值来判断等等，都是可以的