求教一个算法

现在有n种楼,每种楼的面积已知,给定一个地块,地块总面积已知,要求每种楼摆多少个能满足总面积小于地块面积并且此地块不能再放楼的所有组合

2个回答

[code="java"]

public class Demo {

public static void main(String[] args) {

    //第一二三种楼的面积分别为 3 7 11, 假设是整数
    int[] bAreas = {3, 7, 11};
    //某块地的面积
    int availArea = 228;
    //上一次的结果
    int[] result = new int[bAreas.length];
    //收集结果
    List<int[]> list = new ArrayList<int[]>();
    //计算
    calc(bAreas, availArea, 0, result, list);
    //打印结果
    for (int[] is : list) {
        for (int i : is) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

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);

    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);
        }

    }
    list.add(result);
}

}

[/code]

feizhuzi
feizhuzi 分而治之 比较简单的优化策略
7 年多之前 回复
feizhuzi
feizhuzi 递归必然会出现这种情况,我的算法完全没经过优化,你或者用一些数学方法简化下计算,本质上是求多方方程解组合,你看看能不能改进下,然后跟我分享吖O(∩_∩)O
7 年多之前 回复
fxhbeyond
fxhbeyond 当楼的种类达到10的时候 这段程序需要运行2个小时才能出结果 我看您这是for循环立面进行的递归 能够有改进吗
7 年多之前 回复
feizhuzi
feizhuzi list怎么会越界?我的list是存结果,你有多少个结果就打印多少个嘛!算法之外的问题你就自己琢磨吧~O(∩_∩)O~~收分收分~哈哈哈
7 年多之前 回复
fxhbeyond
fxhbeyond 怎么给您分呢??第一次提问 不清楚
7 年多之前 回复
fxhbeyond
fxhbeyond 您这段代码的思路和我想的一样 不过我写半天没写出来 呵呵 非常感谢 不过这样有个小问题 当楼的种类太多的话 list就越界了 我想想怎么处理吧
7 年多之前 回复

谷歌 背包问题

fxhbeyond
fxhbeyond 没有其他条件了 其他条件都是在算出要哪些楼之后才能进行比对的 应该是你说的属于线性规划的范围 多元一次方程
7 年多之前 回复
feizhuzi
feizhuzi 说错了,是线性规划
7 年多之前 回复
feizhuzi
feizhuzi 如果没有别的条件,这就是多元一次方程,你懂的!!
7 年多之前 回复
feizhuzi
feizhuzi 题目还有别的要求么,是求一个解还是多个解,有最优条件么?
7 年多之前 回复
fxhbeyond
fxhbeyond 您好 背包问题貌似是当一个东西放入后不能放入第二次 但我这同一个楼可以多次放入 有其他经典算法能解决这个问题么
7 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问