日期:2014-05-20 浏览次数:20989 次
for(int i=0;i<B.size(),i++) { 球 q = B.get(i); boolean f = false;//判断是否放入了球 for(int j=0;j<A.size(),j++) { 盒子 h = A.get(j); int x = 0;//盒子里球的总重量 for(int k=0;k<盒子h中球的数量,k++) { x += h.get第k个球.get球的重量 } if(x+q.重量<盒子最大容量) { 把第i个球q,放入第j个盒子里。 f = true; break;//放下一个球。 } } if(!f) { //说明现在的盒子都已经满了。或者是第一次循环的时候A里没盒子 //这个时候new 一个盒子放入到数组A里,然后把球q放入这个新盒子里 盒子 h1 = new 盒子(); h1.add(q); A.add(h1); } }
------解决方案--------------------
可以使用BFD(best fit decreasing)算法,但不一定是最优解。
已使用的盒子按剩余容量升序排列,物品按重量降序排列
将物品放入第一个可以放入的盒子,如果没有,拿一个空的放入。
放入后,对已使用的盒子再排序。
------解决方案--------------------
这种问题,可以用回溯法来处理
思路,先计算出最少要用多少个盒子,也就是
盒子数 = 球的总总量 / 盒子的容量
如果刚好整除,盒子数就是最少盒子数,如果不能整除(说明有剩余),则盒子数+1
然后遍历所有球让每个盒子都尝试去装球,如果遍历下来,球更好能装完,则问题解决,如果不能装完,则会退到上一次装球的状态,换另一个球尝试,所有可能尝试结束,还是不能装完,则再会退到上上次装球的状态,如此循环,不断的回退,尝试新的装球,直到找出某个装球方法刚好满足盒子用完球也装完,否则,如果一直回退到最开始没有装球的状态,说明本题无解,也就是给定的盒子不能装完所有的球(如果球和盒子都是符合规则的,一般不会出现这种结果,只有球和盒子不符合规则,比如1个球的重量大于盒子的容量,没有盒子能装这个球,所以无解)。
给出一段代码例子
import java.util.*; public class Test { public static void main(String[] args) throws Throwable { //double[] balls = {6, 3, 3, 2, 2, 2, 2}; //double[] balls = {1, 2, 2, 7, 8}; double[] balls = {6, 3, 3, 2, 2, 2, 2, 1, 2, 2, 7, 8}; //测试用球 double full = 10; //盒子容量 double sum = 0; //所有球的总重量 for (double d : balls) { sum += d; } int count = (int)(sum / full); //计算最少需要的盒子数 if (count < sum / full) count++; double[] weight = new double[count]; //每个盒子已装球的总重量 List<List<Integer>> boxes = new ArrayList<List<Integer>>();//盒子保存的球的下标 for (int i=0; i<count; i++) { boxes.add(new LinkedList<Integer>()); } List<Integer> loaded = new LinkedList<Integer>(); //已装裁过的球的下标 List<List<Integer>> used = new ArrayList<List<Integer>>(); //尝试过的装载 for (int i=0; i<balls.length; i++) { //也就是记录按装载顺序装载过的球的下标 used.add(new LinkedList<Integer>()); } int box = 0, index = 0; while (loaded.size() < balls.length) { //装载的球少于所有的球则循环 if (box == count) { //如果尝试到最后一个盒子结束 if (loaded.size() == 0) { //如果回退到最开始一个球也没装载的状态,则无解 System.out.println("no result"); return; } for (int i=used.size()-1; i>=loaded.size(); i--) { used.get(i).clear(); //回退到某个状态时,该状态以后的状态清空(也就是该状态以后的状态初始化) } index = loaded.remove(loaded.size() - 1); //回退,取出最后一次装载的球 for (box=count-1; box>=0; box--) {//还原上一次装载状态 if (boxes.get(box).contains(index)) { //找到最后一次装载的盒子 weight[box] -= balls[index]; //去掉最后一次转载的球,并还原状态 index = boxes.get(box).indexOf(index); boxes.get(box).remove(index); break; } } } for (int i=0; i<balls.length; i++) { //遍历所有的球,尝试把球装到盒子里 if (loaded.contains(i)) continue; //如果球被装载了,则换下个球 if (used.get(loaded.size()).contains(i)) continue; //如果球装载尝试过了,则换下一个球 if (full-weight[box] >= balls[i]) { //如果盒子还能装球 weight[box] += balls[i]; used.get(loaded.size()).add(i); //记录装载顺序的球的下标 loaded.add(i); boxes.get(box).add(i); } } box++; //下一个盒子 } System.out.println("-------分配结果---------"); for (List<Integer> b : boxes) { System.out.print("{ "); for (int i : b) { System.out.printf("%.2f ", balls[i]); } System.out.println("}"); } } }