日期:2014-05-19 浏览次数:20670 次
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++; } }
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); }