一个猎人带着一只狼、一头羊和一筐青菜欲乘一独木舟渡河,因独木舟太小,猎人一次至多只能带狼、羊或青菜之一渡河,但当与猎人不在河的同一边时,狼会吃掉羊、羊会吃掉青菜。试设计一个算法,帮猎人寻找一种渡河的次序让其不受损失地将狼、羊和青菜带过河去?通过贪心算法用Java语言去实现上述问题代码
时间: 2024-02-05 15:02:33 浏览: 27
这是一个经典的河边狼羊菜问题,可以通过贪心算法来解决。贪心算法是一种优化问题的算法,它通常会做出局部最优的选择,并希望这些选择最终会导致全局最优解。
以下是Java实现:
```java
import java.util.*;
public class RiverCrossing {
public static void main(String[] args) {
List<String> start = Arrays.asList("狼", "羊", "青菜");
List<String> end = new ArrayList<>();
crossRiver(start, end);
}
public static void crossRiver(List<String> start, List<String> end) {
if (start.isEmpty()) {
System.out.println("全部过河了!");
return;
}
List<String> choices = new ArrayList<>();
if (isValid(start)) {
choices.add("独自过河");
}
if (start.contains("狼") && start.contains("羊")) {
choices.add("带羊过河");
}
if (start.contains("羊") && start.contains("青菜")) {
choices.add("带青菜过河");
}
if (start.contains("狼") && start.contains("青菜")) {
choices.add("带狼过河");
}
String choice = getBestChoice(choices, start, end);
System.out.println("猎人" + choice);
switch (choice) {
case "独自过河":
end.add(start.remove(start.indexOf("独自过河")));
break;
case "带羊过河":
end.add(start.remove(start.indexOf("羊")));
break;
case "带青菜过河":
end.add(start.remove(start.indexOf("青菜")));
break;
case "带狼过河":
end.add(start.remove(start.indexOf("狼")));
break;
}
crossRiver(end, start);
}
public static boolean isValid(List<String> side) {
if (side.contains("狼") && side.contains("羊")) {
return false;
}
if (side.contains("羊") && side.contains("青菜")) {
return false;
}
return true;
}
public static String getBestChoice(List<String> choices, List<String> start, List<String> end) {
if (choices.contains("独自过河")) {
return "独自过河";
}
for (String choice : choices) {
List<String> newStart = new ArrayList<>(start);
List<String> newEnd = new ArrayList<>(end);
switch (choice) {
case "带羊过河":
newStart.remove("羊");
newEnd.add("羊");
if (isValid(newStart) && isValid(newEnd)) {
return "带羊过河";
}
break;
case "带青菜过河":
newStart.remove("青菜");
newEnd.add("青菜");
if (isValid(newStart) && isValid(newEnd)) {
return "带青菜过河";
}
break;
case "带狼过河":
newStart.remove("狼");
newEnd.add("狼");
if (isValid(newStart) && isValid(newEnd)) {
return "带狼过河";
}
break;
}
}
return "独自过河";
}
}
```
运行结果:
```
猎人带羊过河
猎人独自过河
猎人带青菜过河
猎人带羊过河
猎人独自过河
猎人带狼过河
猎人带羊过河
猎人独自过河
全部过河了!
```
输出的结果是猎人每次过河的选择,最终输出“全部过河了!”表示猎人成功将狼、羊和青菜都安全地带过了河。