本题的基本解法是使用深度优先搜索算法，仍然是入门难度，但比其他的问题稍稍困难一点的地方在于需要针对性地剪枝，非常经典，值得深入研究。
有一些长度相等的木棍，把它们随机切开，会得到另外一组木棍。已知切削后的木棍长度，求可能的最小原有木棍长度。本题中原有木棍和切削后木棍的长度均保证为整数。
本题会有多次输入数据测试，多次输入以换行作为分隔。每次输入有两个部分组成，以换行符分隔为两行：第一行的整数标明第二行数据的个数；第二行的多个整数以空格分隔，表示切削后的木棍长度。示例输入为：
1
2
3
4
5
| 9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
|
对每组输入数据，输出最小原有木棍长度。实例输出为：
深度优先搜索是图论算法中最基本也是最重要的算法之一，和广度优先搜素一起组成树的常用搜索算法。本算法要求尽可能的深地搜索树的分支，如果对应节点的所在边都己被搜索过，搜索将回溯到发现这个节点的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，属于盲目搜索。
实现方法为：
- 构造辅助数组以记录节点访问状态
- 从根节点出发开始搜索
- 如果当前搜索路径符合要求则搜索成功，退出搜索程序
- 搜索当前节点的子节点：如果未访问则计入搜索路径，而且更改节点状态为已访问；否则，跳过这个子节点，直到找到一个为访问过的子节点
- 如果存在步骤 3 中要求的子节点，则再从这个子节点开始新的搜索
- 如果不存在步骤 3 中要求的子节点，则表示当前搜索路径已达到尽头，应该回溯到上一个搜索启动节点，即上上一个搜索启动节点的下一个子节点，同时为了保证其他搜索路径不出错，将当前启动节点状态记为未访问
- 不断重复 3 到 6 的步骤，直到搜索完全部节点，如果还没有答案则表示带搜索的目标不存在
一般深度优先搜索都使用递归方法描述，用 Java 格式的伪代码表示为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| /**
* DFS核心伪代码
* 前置条件是visit数组全部设置成false
* @param n 当前开始搜索的节点
* @param d 当前到达的深度，也即是路径长度
* @return 是否有解
*/
bool DFS(Node n, int d){
if (d == TARGET){//路径长度为目标长度则返回true，表示此次搜索有解
return true;
}
for (Node nextNode in n){//遍历跟节点n相邻的节点nextNode，
if (!visit[nextNode]){//未访问过的节点才能继续搜索
//例如搜索到节点V1了，那么节点V1要设置成已访问
visit[nextNode] = true;
//接下来要从V1开始继续访问了，路径长度当然要加1
if (DFS(nextNode, d+1)){//如果搜索出有解
//例如到了节点V6，找到解了，你必须一层一层递归的告诉上层已经找到解
return true;
}
//重新设置成未访问，因为它有可能出现在下一次搜索的别的路径中
visit[nextNode] = false;
}
//到这里，发现本次搜索还没找到解，那就要从当前节点的下一个节点开始搜索。
}
return false;//本次搜索无解
}
|
剪枝是 ACM 解题方法中常用到的技巧，经常用来减少搜索等暴力算法的运算时间。剪枝的比喻很能说明问题，就是在数型数据结构的搜索中去掉无意义枝杈的搜索，以加速程序的运行。
一般来说，剪枝的逻辑和每个题目息息相关，题目之间各有不同，需要根据题目分析判断在哪里剪枝才能加速程序。一般要注意，题目中给出的数据范围、数据相互直接的逻辑关联，以及自己能够推导出的联系或公式。
本题看似给出的条件不多，实际是因为有暗含的条件需要解题者自己推理：
- 原来的长度必定可以整除所有木棍长度的和
- 原来的长度必定不小于输入数据中的最大值
这样我们可以先把所有木棍长度求和记为 sum，同时确定木棍长度最大值，从最大值开始，实验 sum 的因子，直到 sum 本身找出符合题目要求的数。
对于每一个确定的因子，假设它是符合要求的长度，那么就可以使用现有的木棍拼接成长度等于因子的多个木棍。关键在于怎么拼接木棍。
实际上，我们应该降序排列木棍的长度，从最长的木棍开始拼接，因为相对来说短的木棍可以适应更多可能的拼接情况即“更灵活”，长木棍拼接法相对较少更易处理。
这样对于给定的长度 len、木棍总长度 total 有拼接好的木棍数量 num = total / len拼接办法有：
- 取出未使用的最长木棍，用
len 减去取出的木棍长度 - 从大到小搜索，保证拼接后的木棍不大于
len：长度相等即拼接成功则拼接数 n 加一，重新开始步骤 1；小于 len 则继续搜索可能的木棍，将已拼接好的长度累加，重新开始步骤 2 - 不断重复 1 和 2，并把所有使用的木棍记上标记，直到拼好的木棍数量为
num，表明 len 是合法的长度 - 如果检查了所有的拼接方案，都不能拼接出
num 个长度为 len 的木棍，则说明这个长度不符合要求
乍一看，数据动态变化很大，相互之间关系不好分辨，很难明白使用什么样的数据结构来组织数据。实际上，对于每个特定的 len，可以拼接的长度范围是固定的，就是所选木棍长度不大于 len 减去已经拼接好的长度。而后，我们要依次拼接这些可行的木棍，并且不断重复这样的过程。对这样分层讨论，层层递进，并且有一对多的关系，可以考虑构造树形结构。
每个树形结构的节点都是拼接的木棍的长度，子节点为拼接方案的候选木棍长度，一旦拼接一根木棍成功，则子节点为下一次拼接的可以使用的最长木棍长度。如此，则题目的解就要求，构造的树高度为木棍的数目，且必须有一条根到叶子的路径包含所有木棍长度，而且符合拼接要求。
这样就能够确定题目解法应该为深度优先搜索。
对于以下输入数据
1
2
| 9
8 3 8 15 2 11 4 8 1
|
有构造的树和正确的构造路径如下所示：
构造路径为 15-3-2-11-8-1-8-8-4，木棍长度为 20。
搜索中会遇到几种情况，可以直接跳出搜索过程，判定当前长度并非答案，比如：
- 当前最长的木棍匹配失败
- 当前拼接成功，但是剩下的无法拼接成功
- 剩余未使用木棍的长度和小于要拼接的长度
同时，要注意到，输入的数据中长度会重复，那么一个木棍匹配失败，和它等长的木棍也就没有必要搜索了。
使用基本的深度优先搜索构造的代码如下（注意：并非正确答案，仅仅是为了说明）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
*
*/
public class Main {
private static int n;
private static int[] sticks = new int[64];
private static boolean[] used = new boolean[64];
private static int length;
private static int numOfSticks;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
while ((n = Integer.parseInt(reader.readLine())) != 0) {
int total = 0;
String tmp = reader.readLine();
int index = 0;
for (String str : tmp.split(" ")) {
int t = Integer.parseInt(str);
total += t;
sticks[index++] = t;
}
Arrays.sort(sticks, 0, n);
for (int i = sticks[n - 1]; i <= total; i++) {
if (total % i != 0) continue;
length = i;
numOfSticks = total / length;
if (search(0, n - 1, 0)) {
System.out.println(i);
break;
}
}
for (int i = 0; i < n; i++) {
used[i] = false;
}
}
}
private static boolean search(int currentLength, int nextStick, int numOfUsedStick) {
if (currentLength == length) {
currentLength = 0;
nextStick = n - 1;
numOfUsedStick++;
}
if (numOfUsedStick == numOfSticks) {
return true;
}
for (; nextStick >= 0; nextStick--) {
if (used[nextStick]) continue;
if (currentLength + sticks[nextStick] <= length) {
used[nextStick] = true;
if (search(currentLength + sticks[nextStick], nextStick - 1, numOfUsedStick)) {
return true;
}
used[nextStick] = false;
}
}
return false;
}
}
|
程序中的 search() 方法使用了基本的深度优先搜索，实际上可以得出正确的数值，但是效率较低，需要进一步优化。
可以 AC 的代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
*
*/
public class Main {
private static int n;
private static int[] sticks = new int[64];
private static boolean[] used = new boolean[64];
private static int length;
private static int numOfSticks;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
while ((n = Integer.parseInt(reader.readLine())) != 0) {
int total = 0;
String tmp = reader.readLine();
int index = 0;
for (String str : tmp.split(" ")) {
int t = Integer.parseInt(str);
total += t;
sticks[index++] = t;
}
Arrays.sort(sticks, 0, n);
for (int i = sticks[n - 1]; i <= total; i++) {
if (total % i != 0) continue;
length = i;
numOfSticks = total / length;
if (search(0, n - 1, 0)) {
System.out.println(i);
break;
}
}
for (int i = 0; i < n; i++) {
used[i] = false;
}
}
}
private static boolean search(int currentLength, int nextStick, int numOfUsedStick) {
if (currentLength == length) {
currentLength = 0;
nextStick = n - 1;
numOfUsedStick++;
}
if (numOfUsedStick == numOfSticks) {
return true;
}
while (nextStick >= 0) {
if (!used[nextStick]) {
if (currentLength + sticks[nextStick] <= length) {
used[nextStick] = true;
if (search(currentLength + sticks[nextStick], nextStick - 1, numOfUsedStick)) {
return true;
}
// 本次搜索失败
used[nextStick] = false;
// 最长木棍匹配失败
if (currentLength == 0) break;
// 当前匹配成功，但是剩余的无法合成
if (currentLength + sticks[nextStick] == length) break;
}
// 如果本次匹配失败，忽略和它等长的木棍
int i = nextStick - 1;
while (i >= 0 && sticks[i] == sticks[nextStick]) i--;
nextStick = i;
// 剩余木棍长度和小于要求，则无需继续搜索
int sumOfLastSticks = 0;
for (; i >= 0; i--) {
if (!used[i]) sumOfLastSticks += sticks[i];
}
if (sumOfLastSticks < length - currentLength) break;
continue;
}
nextStick--;
}
return false;
}
}
|