小猫爬山 DFS

十五月明 1年前 回复TA

这个顺序确保了我们尝试了所有可能的放置方案：

我们首先尝试将小猫放入已有的任何一辆车中。
如果所有已有车辆都无法放入当前小猫，我们才尝试新增一辆车。

十五月明 1年前 回复TA

@十五月明 这个顺序确保了我们尝试了所有可能的放置方案：  我们首先尝试将小猫放入已有的任何一辆车中。 如果所有已有车辆都无法放入当前小猫，我们才尝试新增一辆车。

十五月明 1年前 回复TA

为什么是先for (int i = 0; i < cnt; i++)完全遍历，之后才
    sum[cnt] = a[u]; // 新增一辆车，初始重量是当前猫的重量
    dfs(u + 1, cnt + 1);
    sum[cnt] = 0;

    这个顺序是为了尝试所有可能的放置小猫的方案，并找到需要的最少车辆数。这个顺序反映了深度优先搜索（DFS）算法的回溯特性。下面是代码逻辑的详细解释：
遍历所有已有车辆：
for (int i = 0; i < cnt; i++) 这个循环遍历所有已有的车辆（即cnt辆车）。对于每一辆车，我们检查是否可以将当前的小猫（第u只小猫）放入这辆车中，而不超出车辆的最大载重量w。

如果可以放入，我们将小猫的重量加到这辆车的当前载重sum[i]上，然后递归调用dfs(u+1, cnt)，尝试放入下一只小猫。
递归返回后，我们需要撤销这个操作（回溯），所以我们将小猫的重量从sum[i]中减去，恢复到原来的状态。
尝试新增一辆车：
在尝试了所有已有车辆后，我们再尝试新增一辆车来放置当前的小猫。这是通过sum[cnt] = a[u];实现的，我们将当前小猫的重量作为新增车辆的初始载重。

然后，我们递归调用dfs(u+1, cnt+1)，尝试放入下一只小猫，同时使用新增的这辆车。
递归返回后，我们再次回溯，将新增车辆的载重sum[cnt

发表评论 取消回复