Poj_1011_Sticks(剪枝)

一、Description

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。

Input

输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。

Output

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

二、问题分析

网上找到的题解，很棒：http://www.cppblog.com/y346491470/articles/155318.html

【题解】：下面说下几个重要的剪枝：

1.把所有木棍的长度从大到小排列，组合木棒时优先使用长的木棍，这样可以加快组合速度，并且对后面的剪枝有帮助。

2.木棒的长度一定是大于等于最长木棍的长度并且小于等于所有木棍长度的和，这个很容易证明。

3.木棒的长度一定是所有木棍长度的和的约数，这个也很容易证明。

4.在某一个木棒的组合过程中，对于当前的木棍stick[i]，如果stick[i-1]没有被组合并且stick[i] == stick[i-1]，那么不用考虑stick[i]，显然stick[i]最终也不会被组合。

5.如果此次是在尝试第i个木棒的第一段，假设stick[j]为当前可以被使用的最长的木棍，如果此次组合失败，直接退出搜索，即退回到对第i-1个木棒的搜索。试想：失败说明现在使用stick[j]是不可行的，那么以后无论什么时候使用stick[j]都是不可行的，因为以后再处理stick[j]时可使用的木棍一定是当前可使用的木棍的子集，在更多木棍选择的情况下都不能组合成功，那么，在更少木棍选择的情况下一定不能组合成功。

三、问题解决

第一次听到“剪枝”：没有正式的解释，大概意思是：就是在做搜索的时候，当你确定某些决策一定不可能得到答案的时候，就不必再搜索这个决策了，这样可以减少搜索量，加快程序速度，对于具体的问题是需要一些技巧的，最常见的就是可行性剪枝（当前状态一定不会出解）和最优性剪枝（当前状态即使出解了也一定不会最优）了。

这个问题涉及到排序和搜索算法，我用了QS和DFS。

import java.util.Scanner;

public class N1011_Sticks{
	
	static int[] sticks;
	static boolean[] visited;
	static int n;
	static int st;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while ((n = scan.nextInt()) != 0) {
			int sum = 0;
			sticks = new int[n];
			visited = new boolean[n];
			for (int i = 0; i < n; i++) {
				sticks[i] = scan.nextInt();
				sum += sticks[i];
			}
			quicksort(0, n - 1);
			boolean flag = false;
			for (int ini = sticks[0]; ini < sum; ini++) {
				if (sum % ini == 0 && dfs(0, 0, ini, 0)) {
					System.out.println(ini);
					flag = true;
					break;
				}
			}
			if (!flag) {
				System.out.println(sum);
			}
		}
	}

	static boolean dfs(int len, int s, int ini, int am) {
		if (am == n) {
			return true;
		}

		int sp = -1;

		for (int i = s; i < n; i++) {
			if (visited[i] || sticks[i] == sp) {
				continue;
			}
			visited[i] = true;
			if (len + sticks[i] < ini) {
				if (dfs(len + sticks[i], i, ini, am + 1)) {
					return true;
				} else {
					sp = sticks[i];
				}
			} else if (len + sticks[i] == ini) {
				if (dfs(0, 0, ini, am + 1)) {
					return true;
				} else {
					sp = sticks[i];
				}
			}
			
			visited[i] = false;

			if (len == 0) {
				return false;
			}
		}
		return false;
	}

	static void quicksort(int p, int r) {
		if (p < r) {
			int a = part(p, r);
			quicksort(p, a - 1);
			quicksort(a + 1, r);
		}
	}

	static int part(int p, int r) {
		int x = sticks[r];
		int i = p - 1;
		int j = p;
		for (; j < r; j++) {
			if (sticks[j] > x) {
				i++;
				int k = sticks[i];
				sticks[i] = sticks[j];
				sticks[j] = k;
			}
		}
		int k = sticks[i + 1];
		sticks[i + 1] = sticks[j];
		sticks[j] = k;
		return i + 1;
	}
}