求大牛帮忙优化一段程序解决办法

求大牛帮忙优化一段程序
待优化程序是这样的：

Java code

import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Test {      //现在有n种楼，每种楼的面积已知，    //给定一个地块，地块总面积已知，要求每种楼摆多少个能满足总面积小于地块面积并且此地块不能再放楼的所有组合         //统计结果工多少条    private static int i;    public static void main(String[] args) {                   //第一二三种楼的面积分别为 3 7 11, 假设是整数         int[] bAreas = {8000,3000,4000,4500,5000,5500};          //某块地的面积           int availArea = 200000;          //上一次的结果         int[] result = new int[bAreas.length];          //收集结果           List<int[]> list = new ArrayList<int[]>();          calc(bAreas, availArea, 0, result, list);          System.out.println(i);    }        public static void calc(int[] bAreas, int availArea, int from, final int[] lastResult, List<int[]> list) {          int countOfKind = bAreas.length;          int leftArea = availArea;          int[] result = Arrays.copyOf(lastResult, countOfKind);          int sum=0;          for (int i = from; i < countOfKind; i++) {              int bArea = bAreas[i];              int bCount = leftArea / bArea;              result[i] = bCount;              leftArea = leftArea % bArea;                                      //递归              int recursionTimes = bCount;              int nextLeftArea = leftArea;              int[] nextResut = Arrays.copyOf(result, countOfKind);              while( (i != countOfKind - 1) && recursionTimes > 0){                  nextLeftArea += bArea;                  nextResut[i] = --recursionTimes;                  calc(bAreas, nextLeftArea, i+1, nextResut, list);              }                        }          for(int i = 0;i < result.length;i++){            System.out.print(result[i]+" ");            sum+=(result[i]*bAreas[i]);        }        System.out.println();        //每种方案的所有楼的面积总数        System.out.println(sum);        i++;    }        }  

此程序用的循环里面进行递归调用，肯定会很慢，当我的楼的数组增加到10种的时候 需要几个小时才能求出所有结果 请大牛帮忙优化一下 如果有其他更好的不用递归的算法 那更好了

[解决办法]

探讨

引用:

分析一下，首先，最少可以摆 200000/8000 = 25 栋楼，最多可以摆 200000/3000 = 66 栋楼
6种楼型从25到66种排列分布，这个数量级还是蛮大的，除非算法有所改进，穷举的话优化空间不大，可以采用stack把递归改成非底归试试看

请教一下：怎么用栈把递归改成非递归

[解决办法]
为了表示支持，我写了个递归的：
楼栋：{ 8000, 3000, 4000, 4500, 5000, 5500 }
总方案数: 936316
耗时: 30ms

Java code

import java.util.Arrays;public class BuildingCalculate {    public static void main(String[] args) {        int[] bAreas = { 8000, 3000, 4000, 4500, 5000, 5500 };        //int[] bAreas = { 150000, 100000, 50000, 10000 };        //int[] bAreas = { 150000, 100000, 90000 };        //int[] bAreas = { 100000, 1000 };        //int[] bAreas = { 150000, 250000 };        //int[] bAreas = { 8000 };        //某块地的面积           int availArea = 200000;        //收集结果        long timer = System.currentTimeMillis();        int total = calculate(availArea, bAreas);        timer = System.currentTimeMillis() - timer;        System.out.println("Total: " + total + "\t\tSpend: " + timer + "ms");    }    /**     * 计算填充方案数     * 总体思路：     * 1、将楼栋面积排序；     * 2、从大楼栋开始填充，依次从最大可能～0栋；     * 3、---- 将剩余面积递归尝试用次大楼栋填充；     * 4、如果当前楼栋已经是面积最小的，则无需递归，剩余面积直接填满即可；     * @param totalAvailArea 总可用面积     * @param bAreas 各楼栋面积     * @return 总方案数     */    public static int calculate(int totalAvailArea, int[] bAreas) {        Arrays.sort(bAreas); // 将楼栋面积进行排序（其实不排也行，排序的好处是检查结果时自己算起来方便）        System.out.println("AfterSort: " + Arrays.toString(bAreas) + "\n");        return recursive(totalAvailArea, bAreas, bAreas.length - 1);    }    /**     * 递归计算     * @param availArea 可用面积     * @param bAreas 各种楼栋面积     * @param p 当前填充楼栋在数组中的位置     */    private static int recursive(int availArea, int[] bAreas, int p) {        int sum = 0; // 方案的汇总数        int max = availArea / bAreas[p]; // 当前楼栋最多可建筑（填充）多少套        if (p > 0) { // 并非最小的楼栋，所以还可以继续递归            for (int num = max; num >= 0; num--) { // 从最多套数～0套                displayResult(bAreas, p, num);                sum += recursive(availArea - bAreas[p] * num, bAreas, p - 1); // 递归计算次大面积楼栋的填充方案            }        } else { // 已经是最小楼栋了，方案唯一：必然就是直接将剩余空间填满而已            displayResult(bAreas, p, max);            return sum = 1;        }        return sum;    }    /**     * 只是显示下结果而已     * @param bAreas 各种楼栋面积     * @param p 当前填充楼栋在数组中的位置     * @param num 当前楼栋最多可建筑（填充）的套数     */    private static void displayResult(int[] bAreas, int p, int num) {        if (bAreas.length < 5) { // 规模太大的话，结果太多屏幕输出太慢了，要改成写文件才行            for (int i = p + 1; i < bAreas.length; i++) {                System.out.print("\t");            }            System.out.println("[" + (bAreas.length - p) + ":" + bAreas[p] + "]*" + num);        }    }} 
  

 

查看更多 下一篇