求大牛帮忙优化一段程序

Question

待优化程序是这样的：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种的时候 需要几个小时才能求出所有结果 请大牛帮忙优化一下  如果有其他更好的不用递归的算法 那更好了

Answer 1

aX+bY+cZ<sum  and (aX+bY+c)>100-min(a,b,c)
今天没时间了，什么时候试一试。

Answer 2

嗯 应该算个不考虑价值因素的简单背包问题  但for循环里面套用递归总感觉不好  又没想到其他办法

Answer 3

后面一个不等式没看懂怎么来的(aX+bY+c)>100-min(a,b,c)

Answer 4

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

Answer 5

给你写个非递归的，注视也写了，LZ参考参考吧
import java.util.*;
public class Test {
    public static void main(String[] args) throws Throwable {
        final int[] bAreas = {8000,3000,4000,4500,5000,5500};  
        final int availArea = 200000;        int[] bCounts = new int[bAreas.length]; //每种楼型数量
        bCounts[0] = availArea / bAreas[0]; //初始化第一种楼型最多数量
        int pos = 0, min = availArea, remain = availArea % bAreas[0]; //剩余面积
        for (int a : bAreas) {if (min > a) min = a;} //楼型最小面积
        List<int[]> list = new ArrayList<int[]>(); //结果保存
        
        while (true) { //无条件大循环
            while (remain >= min) { //当剩余面积大于最小楼型面积时
                if (pos+1 == bAreas.length) break; //如果不能满足分配则退出分配
                pos++; //取下一种楼型
                bCounts[pos] = remain / bAreas[pos]; //下一种楼型最大分配
                remain %= bAreas[pos]; //剩余面积
            }            if (remain >= 0 && remain < min) { //如果满足分配
                list.add(Arrays.copyOf(bCounts, bCounts.length)); //保存结果
            }
            
            if (pos == bAreas.length-1) pos--; //如果分配到最后一种楼型，则回到前一种楼型
            for (;pos>=0 && bCounts[pos] == 0; pos--); //不断往前查看前一种楼型是否有分配
            if (pos < 0) break; //如果回到最前都没有分配楼型，则说明分配结束，退出循环            bCounts[pos]--; //如果前一种楼型有分配，则前一种楼型数量-1
            remain = availArea; //重新计算计算剩余面积
            for (int i=0; i<bAreas.length; i++) {
                if (i <= pos) {
                    remain -= bCounts[i] * bAreas[i]; //总面积-前n种楼型消耗的面积
                } else {
                    bCounts[i] = 0; //后m种楼型数量清空
                }
            } //然后回到大循环去重新分配
        }        System.out.printf("total solutions: %d\n", list.size()); //打印总分配方案数量
        Collections.sort(list, new Comparator<int[]>() { //排序找到最好方案
            public int compare(int[] a1, int[] a2) { //LZ可以根据条件自己排序
                int s1=0, s2=0, c1=0, c2=0;
                for (int i=0; i<a1.length; i++) {
                    c1 += a1[i]; //楼型数量
                    c2 += a2[i];
                    s1 += a1[i] * bAreas[i]; //消耗总面积
                    s2 += a2[i] * bAreas[i];
                }
                
                if (s1 == s2) { //消耗总面积相同则楼型数量最多的方案优先
                    return c2 - c1;
                }
                return s2 - s1; //否则消耗总面积最大优先（即剩余面积最小有限）
            }
        });        for (int i=0; i<list.size(); i++) { //打印方案
            int c = 0, s = 0;
            int[] a = list.get(i);
            for (int j=0; j<a.length; j++) {
                System.out.printf("%d:%d ", bAreas[j], a[j]);
                c += a[j]; //楼型数量
                s += a[j] * bAreas[j]; //消耗面积
            }
            System.out.printf("| count:%d remain:%d\n", c, availArea-s); //剩余面积
            if (i == 49) break; //因为方案太多，只打印前50种方案，
                                    //LZ可以把break注视掉打印所有方案
        }
    }
}

Answer 6

为了表示支持，我写了个递归的：
楼栋：{ 8000, 3000, 4000, 4500, 5000, 5500 }
总方案数: 936316
耗时: 30ms
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);
        }
    }
}
输出：
AfterSort: [3000, 4000, 4500, 5000, 5500, 8000]
Total: 936316 Spend: 30ms