装箱问题 装箱问题

问题

假设有编号分别为0、1、……、n-1的n种物品，体积分别为V0、V1、……、Vn-1。将这n种物品装到容量都为V(V=100)的箱子里。约定这n种物品的体积均不超过V，即对于0<=i

思路

用贪心算法解决此问题的思路很简单。就是你要确保每一个箱子里面装的物品是当前最大的量就行，于是你需要对待装入物品按照体积从大到小排个序。然后把当前最大的物品装入箱子里面，然后在剩余的物品中挑选一个能装入箱子剩余空间的最大的物品，以此类推，直到无法再装入任何剩余物品为止。再开始下一个箱子。直到所有物品都被装入箱子，那么算法结束。

使用

package com.company;public class Main { public static void main(String[] args) { // write your code here int[] goodsArray = {35,60,45,20,20,20}; int boxSpace = 100; Solution.fillBoxes(goodsArray,boxSpace); }}

输出

箱子实装:95箱子实装:85箱子实装:20Process finished with exit code 0

实现

package com.company;public class Solution { /** * 用贪心算法来找到装箱问题的最优解 * @param goodsArray * @param boxSpace */ static public void fillBoxes(int[] goodsArray,int boxSpace) { //先排序 Good headerPointer = Solution.sortGoods(goodsArray); Box boxHeader = null; Box currentBoxPointer = null; while (headerPointer.nextPointer != null) { Box currentBox = new Box(boxSpace); if (boxHeader == null) { boxHeader = currentBox; currentBoxPointer = boxHeader; } else { currentBoxPointer.nextPointer = currentBox; currentBoxPointer = currentBox; } Good currentGood = headerPointer; while (currentGood.nextPointer != null) { if (currentGood.nextPointer.getVolume() <= currentBox.getRemainSpace()) { Good tempGood = currentGood.nextPointer; currentGood.nextPointer = currentGood.nextPointer.nextPointer; tempGood.nextPointer = null; currentBox.addGood(tempGood); } else currentGood = currentGood.nextPointer; } } while (boxHeader != null) { System.out.println("箱子实装:" + (boxSpace - boxHeader.getRemainSpace())); boxHeader = boxHeader.nextPointer; } } /** * 给待装箱物品排序 * @param goodsArray * @return */ static private Good sortGoods(int[] goodsArray) { Good header = new Good(-1); Good currentPointer = null; for (int counter = 0;counter < goodsArray.length;counter++) { currentPointer = header; while (currentPointer.nextPointer != null && currentPointer.nextPointer.getVolume() > goodsArray[counter]) currentPointer = currentPointer.nextPointer; Good tempGood = new Good(goodsArray[counter]); tempGood.nextPointer = currentPointer.nextPointer; currentPointer.nextPointer = tempGood; } return header; }}

package com.company;public class Good { public Good nextPointer = null; private int volume = 0; public Good(int volume) { this.volume = volume; } public int getVolume() { return volume; }}

package com.company;public class Box { public Box nextPointer = null; private int remainSpace = 0; private int origialSpace = 0; public Good goodPointer = null; public Box(int origialSpace) { this.origialSpace = origialSpace; this.remainSpace = this.origialSpace; } public int getRemainSpace() { return remainSpace; } /** * 添加商品 * @param good */ public void addGood(Good good) { if (good == null)return; if (goodPointer == null)goodPointer = good; else { goodPointer.nextPointer = good; goodPointer = goodPointer.nextPointer; } remainSpace = remainSpace - goodPointer.getVolume(); }}

本文地址：https://caijingdemo.com/changshi/75050.html