现在有n种楼,每种楼的面积已知,给定一个地块,地块总面积已知,要求每种楼摆多少个能满足总面积小于地块面积并且此地块不能再放楼的所有组合
[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]
谷歌 背包问题