【转】http://blog.csdn.net/shangqing1123/article/details/47661389
/**
* 功能：给你一堆n个箱子，箱子宽wi,高hi，深di。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。
* 实现方法：搭出最高的一堆箱子，箱子堆的高度为每个箱子高度的总和。
*/
两种方法：
方法一：递归法
- public static ArrayList<Box> createStackR(Box[] boxes,Box bottom){
- int maxHeight=0;
- ArrayList<Box> maxStack=null;
-
- for(int i=0;i<boxes.length;i++){
- if(boxes[i].canBeAbove(bottom)){
- ArrayList<Box> newStack=createStackR(boxes,boxes[i]);
- int newHeight=stackHeight(newStack);
-
- if(newHeight>maxHeight){
- maxHeight=newHeight;
- maxStack=newStack;
- }
- }
- }
-
- if(maxStack==null)
- maxStack=new ArrayList<Box>();
-
- if(bottom!=null)
- maxStack.add(0,bottom);
-
- return maxStack;
- }
-
- public static int stackHeight(ArrayList<Box> stack){
- int height=0;
- for(int i=0;i<stack.size();i++){
- height+=stack.get(i).heigth;
- }
- return height;
- }
方法二：动态规划
- public static ArrayList<Box> createStackDP(Box[] boxes,Box bottem,HashMap<Box,ArrayList<Box>> stackMap){
- if(bottem!=null&&stackMap.containsKey(bottem))
- return stackMap.get(bottem);
-
- int maxHeight=0;
- ArrayList<Box> maxStack=null;
-
- for(int i=0;i<boxes.length;i++){
- if(boxes[i].canBeAbove(bottem)){
- ArrayList<Box> newStack=createStackDP(boxes, boxes[i], stackMap);
- int newHeight=stackHeight(newStack);
-
- if(newHeight>maxHeight){
- maxStack=newStack;
- maxHeight=newHeight;
- }
- }
- }
-
- if(maxStack==null)
- maxStack=new ArrayList<Box>();
- if(bottem!=null)
- maxStack.add(0, bottem);
- stackMap.put(bottem, maxStack);
-
-
-
- return (ArrayList<Box>) maxStack.clone();
- }
-
- lt;pre name="code" class="java"><pre name="code" class="java"> public static int stackHeight(ArrayList<Box> stack){
- int height=0;
- for(int i=0;i<stack.size();i++){
- height+=stack.get(i).heigth;
- }
- return height;
- }
箱子
- class Box{
- int width;
- int heigth;
- int depth;
-
- public Box(int width,int heigth,int depth){
- this.width=width;
- this.heigth=heigth;
- this.depth=depth;
- }
-
- public boolean canBeAbove(Box box){
- if(box.width>this.width&&box.heigth>this.heigth&&box.depth>this.depth)
- return true;
- return false;
- }
- }
堆箱子
原文：http://www.cnblogs.com/lucky-star-star/p/5220532.html
