POJ 1011 DFS+剪枝

系统管理员 2024-04-19 11:17 15阅读 0赞

题目是英文的翻译过来大概是这个意思：  
现在有一些长度相同的棍子，将这些棍子随意切割成n个长度不一的棍子。题目会给出n和这n个棍子的长度，求原来棍子长度的最小值。也可以反过来说，给你n个棍子要你将其拼接成几个相同长度的棍子，求其长度的最小值。

这道题要采用DFS + 剪枝，单纯使用DFS会超时。

下面讲解剪枝:  
1、降序排序这没什么好说的

2、n个棍子是由原来的棍子切割而成，设max是n个棍子中的最大值，sum为n个棍子的合。那么棍子可能的长度len应该满足  
max<=len<=sum && sum%len ==0。这样可以去除大部分不可能的长度。

3、跳跃剪枝，当第i个点试探后不能满足结果，那么在i点后面与i点值相同的点不必在试探，因为一定不满足  
例如：15 8 8 8 8 8 2 ...... 假设我们预设的len=17，那么 15+8>17 不满足条件，那15后面第一个8后面的8都不必在试探了因为一定不满足。  
简单证明：  
假设15不能后其后面第一个8凑成预设的长度  
那么15和第一个8后面的8组合也肯定凑不出来  
因为如果15和第一个8组合，那么其还可以选择的数有 8 8 8 8 2...... (1)  
15和非第一个8组合（假设第三个），还可以选择的数有 8 8 2...       (2)  
显而易见（1）可选择的数要包含（2）可选择的数，（1）既然都不能凑成预设长度，那么（2）更加不可能了。

4、当前所选起始点不能满足条件时，不必继续遍历找新的起始点，直接回退，因为这一定是上一层出现了问题。  
例如15 11 8 8 8 4 3 2 1，假设其最小长度为20（结果也确实是20）  
先把15作为起始点，往后遍历可以找到\{ 15 4 1\}=20  
再以11作为起始点，往后遍历发现无法凑成20。  
现在问题来了：我们还要不要往后试探，将8 8 8 4 3 2 1 依次作为新的起始点呢？

答案是没必要的，因为出现这种问题只可能是以前的决策出现了问题，应该回退到15起始点那层重新决策。  
事实也确实如此 ，15如果和3、2凑到一起而不是4、1那么就可以得到最终结果\{15 3 2\}、\{ 8 8 4\}、\{11 8 1\}   
那么你怎么知道就一定是以前的决策出现了问题呢？换一个起始点会不会就能凑出来20了呢？  
其实用简单的反证法就知道：  
前提：问题肯定是有解的、以前的决策没有问题  
那么11肯定会和某几个数凑成20  
但是现在11不能和某几个数凑成20且问题肯定有解，那么只可能是以前的决策存在问题

对于这道题3、4的剪枝是十分重要的，我的代码中注释了3、4的点就对应其剪枝的代码操作。

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    
    /**
     * created by 吴家俊 on 2019/9/17.
     */
    public class Main{
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int count = scanner.nextInt();
            ArrayList<Integer> list = new ArrayList();
            int sum;
            while (count != 0) {
                sum = 0;
                for (int i = 0; i < count; i++) {
                    int k = scanner.nextInt();
                    list.add(k);
                    sum += k;
                }
                Bar bar = new Bar(list, sum);
                bar.inputResult();
                count = scanner.nextInt();
                //清空list
                list.clear();
            }
        }
    }
    
    class Bar {
        private ArrayList<Integer> list;//存储被切后各个棒的长度
        private int[] visit; //访问数组标记某个数是否被使用过 0未使用 1使用
        private int len; //预测最初每个棒的长度
        private int n; //最初棒的个数
        private int sum; //棒的总长度
        private boolean flag; //标记是否得出结果
    
        public Bar(ArrayList<Integer> list, int sum) {
            this.list = list;
            this.sum = sum;
            Collections.sort(list);
            Collections.reverse(list); //按棒长降序排序
        }
    
        private void init() {
            visit = new int[list.size()];
            flag = false;
        }
    
        public void inputResult() {
            for (int i = list.get(0); i <= sum; i++) { //1、缩小len的取值范围
                if (i == sum) {
                    System.out.println(i);
                } else if (sum % i == 0) { //2、再次缩小len的取值范围
                    n = sum / i;
                    len = i;
                    init();
                    dfs(0, len, 0);
                    if (flag) {
                        break;
                    }
                }
            }
        }
    
        /**
         * @param index 遍历的起始下标
         * @param l     当前剩余长度 为0时 表示凑成了一个原先的棒
         * @param now   当前已经凑成的棒的根数 为n时 表示得到解
         */
        private void dfs(int index, int l, int now) {
            if (flag) return;
            if (now >= n) {
                flag = true;
                System.out.println(len);
                return;
            }
            for (int i = index; i < visit.length; i++) {
                if (visit[i] == 0 && l - list.get(i) >= 0) {
                    visit[i] = 1; //标记已访问
                    if (l - list.get(i) == 0) { //凑成了一根棒
                        dfs(0, len, now + 1); //开始寻找下一个棒的起点
                    } else {
                        dfs(index + 1, l - list.get(i), now);
                    }
                    visit[i] = 0; //还原
                    if (flag) return;
                    if (l == len) return; //3、之前的决策有问题，回退到上一根棒的拼凑过程
                    while (i + 1 < visit.length && list.get(i + 1) == list.get(i)) {//4、该点失败后，后面相同的点不用再尝试
                        i++;
                    }
                }
            }
        }
    }