算法分析

题目求的是：可行拼接木棒的最小长度
dfs
从小到大枚举木棒长度

• 1、可行性剪枝：枚举length能整除sum的木棒长度

• 2、优化搜索顺序：木棒从大到小枚举

• 3、排除等效冗余

  • 3-1：按组合数枚举

  • 3-2：如果当前木棍加到当前棒中，失败了，则直接略过后面所有长度相等的木棍

  • 3-3：如果是木棒的第一根木棍失败了，则一定失败，退出

  • 3-4：如果是木棒的最后一根木棍失败了，则一定失败，退出

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 70;
    static int n;
    static int[] w = new int[N];
    static boolean[] st = new boolean[N];
    static int length;
    static int sum;
    static void swap(int i,int j)
    {
        int tmp = w[i];
        w[i] = w[j];
        w[j] = tmp;
    }
    static void reverse()
    {
        int i = 0;
        int j = n - 1;
        while(i <= j) 
        {
            swap(i,j);
            i ++;
            j --;
        }
    }
    static boolean dfs(int u,int s,int start)
    {
        if(u * length == sum) return true;
        if(s == length) return dfs(u + 1,0,0);
        //剪枝3-1,i从start开始枚举
        for(int i = start;i < n;i ++)
        {
            if(st[i]) continue;
            if(s + w[i] > length) continue; //可行性剪枝

            st[i] = true;
            if(dfs(u,s + w[i],i + 1)) return true;
            st[i] = false; //恢复现场

            //剪枝3-3
            if(s == 0) return false;
            //剪枝3-4
            if(s + w[i] == length) return false;

            //剪枝3-2
            int j = i;
            while(j < n && w[i] == w[j]) j ++;
            i = j - 1;
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(true)
        {
            n = scan.nextInt();
            Arrays.fill(st,false);
            if(n == 0) break;
            sum = 0;
            for(int i = 0;i < n;i ++) 
            {
                w[i] = scan.nextInt();
                sum += w[i];
            }
            //从大到小排序
            Arrays.sort(w,0,n);
            reverse();

            length = 1;
            while(true)
            {
                //第0根木棒,拼接长度是0,第0根开始
                if(sum % length == 0 && dfs(0,0,0))
                {
                    System.out.println(length);
                    break;
                }
                length ++;

                if(length > sum) break;
            }
        }
    }
}