1、题目描述
【羊、狼、农夫过河】
羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。
备注：农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。农夫自身不占用船的容量。
【输入描述】
第一行输入为M，N，X， 分别代表羊的数量，狼的数量，小船的容量。
【输出描述】
输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数（若无法满足条件则输出0）。
【示例1】
输入: 5 3 3
输出: 3
说明:第一次运2只狼第二次运3只羊第三次运2只羊和1只狼
【示例2】
输入: 5 4 1
输出: 0
说明:如果找不到不损失羊的运送方案，输出0
2、解题思路
初始化一个变量minTimes为(羊数量+狼数量) *小船容量;
定义一个回溯DFS方法, 用于模拟过河的过程，每次递归计算 当前状态下的最小运输次数;
在DFS函数中，遍历尝试所有可能的运输组合,保证组合中羊的数量大于等于狼的数量,以防止羊被狼吃掉;
在递归过程中，如果发现某种组合能够使得所有羊和狼都运到对岸，且所需次数小于当前记录的最小次数,则更新最小次数;
后输出最小运输次数。如果没有找到满足条件的运输方案，输出0。
3、参考代码
import java.util.Scanner;public class 羊狼农夫过河 { public static int minTimes = Integer.MAX_VALUE; public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int m = in.nextInt(); // 羊数量 int n = in.nextInt(); // 狼数量 int x = in.nextInt(); // 小船数量 minTimes = 0; dfs(m, n, x, 0, 0, 0); if (minTimes == Integer.MAX_VALUE) { System.out.println(0); } else { System.out.println(minTimes); } } } public static int dfs(int m, int n, int x, int m1, int n1, int times) { // 如果小船容量足够运输所有羊和狼，则只需要一次即可 if (x >= m + n) { if (times + 1 < minTimes) { minTimes = times + 1; } return times + 1; } // 遍历所有的运输组合，保证组合中羊的数量大于狼的数量 for (int i = 0; i <= m && i <= x; i++) { for (int j = 0; j <= n && i + j <= x; j++) { if (i + j == 0) { continue; } // 船离岸后，原来这岸，要么没有羊，要么羊比狼多 if ((m - i == 0 || m - i > n - j) && (m1 + i == 0 || m1 + i > n + j)) { int result = dfs(m, n, x, m - i, n - j, times + 1); if (result < minTimes && result != 0) { minTimes = result; } } } } return 0; }}4、相似题目
（1）代码随想录回溯专题
来源地址：https://blog.csdn.net/weixin_43763430/article/details/130717150
