一 问题描述

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

二 输入和输出

1 输入

输入包含多组数据，每组数据都包括两行。第 1 行是一个不超高跟 64  位的整数，表示砍断之后共有多少节木棒。第 2 行是截断以后所得各节木棒的长度。在最后一组数据之后是一个 0 。

2 输出

对每组数据，都单行输出原木棒的最小长度。

三 输入和输出样例

1 输入样例

9

5 2 1 5 2 1 5 2 1

4

1 2 3 4

0

2 输出样例

6

5

四 算法设计

本问题由切割的木棒长度推测原木棒的最小长度，可以枚举原木棒的最小长度，使用回溯法搜索及剪枝优化即可解决。可以用拼接的方法反向推测，根据现有木棒拼接成多个等长的原木棒。例如，1 2 3 4，最多可以拼接成两根等长木棒 4+1、3+2，原来木棒的最小长度为 5.

1 枚举长度

木棒的总长度为 sumlen，最长木棒的长度为 maxlen。因为切割后最长为 maxlen，那么原木棒必然大于等于 maxlen。如果原木棒只有一根，那么原木棒的长度就是 sumlen。如果原木棒多于 一根，那么原木棒的长度一定小于或等于 sumlen/2。从 maxlen 到 sumlen/2，从小到大枚举所有可能的原木棒长度，通过深度优先搜索尝试能够组合成原木棒，如果尝试成功，则说明当前木棒的长度为原木棒的最小可能长度。

2 组合顺序

对木棒长度从大到小排序，如果从小到大排序则会超时。因为小木棒比大木棒灵活性更好，所以先考虑较长的木棒，然后用较短的木棒组合成原棒，更容易成功。好比往箱子里装东西，尽量先装大的，然后用较小的填补空隙，如果先把小的装进去，大的就可能放不下去。用一维数组 used[] 标记当前状态下木棒是否已使用组合原棒。

3 剪枝技巧

• 技巧1：从小到大枚举，第 1 个满足条件的原木棒长度 InitLen 必须是最短的。
• 技巧2：原木棒是等长的，因此 sumlen % InitLen = 0。
• 技巧3：如果当前木棒已使用或者与前一个未使用的木棒长度相等，则无须再搜索。
• 技巧4：组合新木棒时，若搜索完所有木棒后都无法组合，则说明该木棒无法在当前组合方式下组合，不用往下搜索，直接返回上一层。

五 代码

package com.platform.modules.alg.alglib.poj1011;

import java.util.Arrays;
import java.util.Collections;

public class Poj1011 {
    public String output = "";
    private final int maxn = 70;
    private int n;
    private Integer stick[] = new Integer[maxn];
    private boolean used[] = new boolean[maxn];

    public Poj1011() {
        for (int i = 0; i < stick.length; i++) {
            stick[i] = 0;
        }
    }

    boolean dfs(int len, int InitLen, int index, int num) {
        if (num == n)
            return true;
        int prelen = -1;
        for (int i = index; i < n; i++) {
            if (used[i] || stick[i] == prelen)//已使用或与上一个未使用的木棒长度相同
                continue;
            used[i] = true;
            if (len + stick[i] < InitLen) {
                if (dfs(len + stick[i], InitLen, i + 1, num + 1))
                    return true;
                else
                    prelen = stick[i];
            } else if (len + stick[i] == InitLen) {
                if (dfs(0, InitLen, 0, num + 1))
                    return true;
                else
                    prelen = stick[i];
            }
            used[i] = false;//回溯复位
            if (len == 0)
                break;
        }
        return false;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        int n = Integer.parseInt(line[0]);
        String[] words = line[1].split(" ");
        Integer sumlen = 0;
        for (int i = 0; i < n; i++) {
            stick[i] = Integer.parseInt(words[i]);
            sumlen += stick[i];
            used[i] = false;
        }
        Arrays.sort(stick, Collections.reverseOrder());

        int maxlen = stick[0];
        boolean flag = false;
        for (Integer InitLen = maxlen; InitLen <= sumlen / 2; InitLen++) {
            if (sumlen % InitLen == 0 && dfs(0, InitLen, 0, 0)) {
                output = InitLen.toString();
                flag = true;
                break;
            }
        }
        if (!flag)
            output = sumlen.toString();
        return output;
    }
}

六 测试