限定时间内过桥，JAVA程序实现
题目：小明过桥要一秒，小明的弟弟要三秒，小明的爸爸要六秒，小明的妈妈要八秒，小明的爷爷要十二秒。每次此桥最多可过两人，而过桥的速度，依过桥最慢者而定，可是灯在点燃后， 三十秒就会熄灭。那么，请问小明一家，如何在三十秒内过桥？
下面是个简单的实现，还没有进行代码优化，将一定时间范围内的过桥组合都打印出来
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;/** * 小明过桥要一秒，小明的弟弟要三秒，小明的爸爸要六秒，小明的妈妈要八秒，小明的爷爷要十二秒。 * 每次此桥最多可过两人，而过桥的速度，依过桥最慢者而定，可是灯在点燃后， 三十秒就会熄灭。 * 那么，请问小明一家，如何在三十秒内过桥？ * @version 1.0 */public class CrossBridge { private static final String SPEND_TIME = "花费时间: "; private static final String STEPS_ARROW = "步骤-->"; private static final String BACK_ARROW = "<----Back "; private static final String GO_ARROW = "--- >GO"; private static final String RIGHT_BRACKET = "}"; private static final String LEFT_BRACKET = "{"; private static final String LINE_BREAK = "\n"; // 逗号分割符 private static final String COMMA_DELIMITED = ","; // 设置有限的秒数 private static final int LIMITED_SECONDS = 30; // 用于存储人物和过桥时间 private static Map<String, Integer> map = new HashMap<String, Integer>(); static { map.put("A", 1);// 小明过桥要一秒 map.put("B", 3);// 小明的弟弟要三秒 map.put("C", 6);// 小明的爸爸要六秒 map.put("D", 8);// 小明的妈妈要八秒 map.put("E", 12);// 小明的爷爷要十二秒 } /** * * @param source * 需要过桥的人员 * @param target * 已经过桥的人员 * @param elapsedSeconds * 已经花费的时间 * @param steps * 用于记录过桥的经过 */ public void doCrossBridge(List<String> source, List<String> target, int elapsedSeconds, StringBuilder steps) { for (String twoPersonToCross : getAllResultSet(source)) { String[] seperatedPersons = twoPersonToCross.split(COMMA_DELIMITED); List<String> currentSourceToGo = new ArrayList<String>(source); List<String> currentTargetInWaiting = new ArrayList<String>(target); StringBuilder currentStepsToGo = new StringBuilder(steps); int currentTimeFromSource = elapsedSeconds; for (String person : seperatedPersons) { currentSourceToGo.remove(person); currentTargetInWaiting.add(person); } currentTimeFromSource += getLargeSeconds(seperatedPersons[0], seperatedPersons[1]); currentStepsToGo.append(LEFT_BRACKET).append(twoPersonToCross) .append(RIGHT_BRACKET).append(GO_ARROW).append(LINE_BREAK); if (currentSourceToGo.isEmpty()) { if (currentTimeFromSource < LIMITED_SECONDS) { System.out.print(SPEND_TIME); System.out.println(currentTimeFromSource); System.out.println(STEPS_ARROW); System.out.println(currentStepsToGo.toString()); } } else { for (String personToBack : currentTargetInWaiting) { StringBuilder currentStepsToBack = new StringBuilder( currentStepsToGo.toString()); int currentTimeFromTarget = currentTimeFromSource; List<String> currentTargetToBack = new ArrayList<String>( currentTargetInWaiting); currentTargetToBack.remove(personToBack); List<String> currentSourceInWaiting = new ArrayList<String>( currentSourceToGo); currentSourceInWaiting.add(personToBack); currentStepsToBack.append(LEFT_BRACKET) .append(personToBack).append(RIGHT_BRACKET).append( BACK_ARROW).append(LINE_BREAK); currentTimeFromTarget += map.get(personToBack); // 重新调用 doCrossBridge(currentSourceInWaiting, currentTargetToBack, currentTimeFromTarget, currentStepsToBack); } } } } /** * * @param s1 * @param s2 * @return 获取花费过桥时间多的人员的秒数 */ private int getLargeSeconds(String s1, String s2) { return (map.get(s1) >= map.get(s2)) ? map.get(s1) : map.get(s2); } /** * 给定几个人，获取所有的两个人一起过桥的所有的组合 A,B与B,A过桥是一样的，A,A过桥是不可能的，这些情况都要去除 * * @param list * 需要过桥的人员 * @return 获取所有的两个人一起过桥的所有的组合 */ private List<String> getAllResultSet(List<String> list) { List<String> result = new ArrayList<String>(); String[] s = new String[list.size()]; list.toArray(s); for (int i = 0; i < s.length - 1; i++) { for (int j = 0; j < s.length; j++) { if (!s[i].equals(s[j]) && !result.contains(s[i] + COMMA_DELIMITED + s[j]) && !result.contains(s[j] + COMMA_DELIMITED + s[i])) { result.add(s[i] + COMMA_DELIMITED + s[j]); } } } return result; } public static void main(String[] args) { List<String> list = new ArrayList<String>(); list.add("A"); list.add("B"); list.add("C"); list.add("D"); list.add("E"); new CrossBridge().doCrossBridge(list, new ArrayList<String>(), 0, new StringBuilder()); }}