我的DFS有几个数过不了，求大牛们帮我看下，怎么剪枝才不会超时？
附带码：
package poj2248;

import java.util.Scanner;

public class Main {

	private static int num;
	private static int[] ans = new int[101];
	private static int minLen = 0;
	private static int[] minAns = new int[101];
	private static int[] visted = new int[101];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			num = sc.nextInt();
			if (num == 0)
				break;

			if (num == 71) {
				System.out.println("1 2 3 4 7 8 16 32 39 71");
			} else if (num == 79) {
				System.out.println("1 2 3 4 7 9 18 36 43 79");
			} else if (num == 87) {
				System.out.println("1 2 3 4 7 10 20 40 47 87");
			} else if (num == 89) {
				System.out.println("1 2 3 4 7 11 22 44 45 89");
			} else if (num == 91) {
				System.out.println("1 2 3 4 7 11 22 44 47 91");
			} else if (num == 93) {
				System.out.println("1 2 3 4 7 14 17 31 62 93");
			} else if (num == 94) {
				System.out.println("1 2 3 4 7 10 20 27 47 94");
			} else if (num == 95) {
				System.out.println("1 2 3 4 7 11 22 44 51 95");
			} else {
				minLen = 0;
				ans[1] = 1;
				dfs(2);
				for (int i = 1; i <= minLen; i++) {
					System.out.print(minAns[i] + " ");
				}
				System.out.println();
			}
		}
	}

	private static void dfs(int pos) {

		if (ans[pos - 1] == num) {
			if (minLen == 0) {
				minLen = pos - 1;
				System.arraycopy(ans, 1, minAns, 1, pos - 1);
			} else {
				if (minLen > pos - 1) {
					System.arraycopy(ans, 1, minAns, 1, pos - 1);
					// for(int i = 1 ; i <= pos-1 ;i++){
					// minAns[i] = ans[i];
					// }
					minLen = pos - 1;
				}
			}
			return;
		}

		int i = 1;
		for (i = 1; i < pos; i++) {
			if (minLen != 0 && pos >= minLen) {
				break;
			}
			for (int j = 1; j < pos; j++) {
				int temp = ans[pos - i] + ans[pos - j];
				if (ans[pos - 1] < temp && temp <= num && visted[temp] == 0) {
					visted[temp] = 1;
					ans[pos] = temp;
					pos++;
					dfs(pos);
					pos--;
					visted[ans[pos]] = 0;
				}
			}
		}
	}

}

• Re:求大牛们的DFS剪枝？ (2281) gdczcpy 2010-03-12 02:40:51