9.9递归和动态规划(十)——堆箱子

2015年8月14日 8点热度 0条评论 来源: half1_2_1

/**

 * 功能:给你一堆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);
		
		/**
		 * 方法clone()来自Object类,其方法签名如下:重写方法时,可以调整参数,但不得改动返回类型。
		 * 因此,如果继承自Object的类重写了clone()方法,它的clone()方法仍将返回Object实例。因此必须转型返回值。
		 */
		
		return (ArrayList<Box>) maxStack.clone();//返回副本	
	}

<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;
	}
}

    原文作者:half1_2_1
    原文地址: https://blog.csdn.net/shangqing1123/article/details/47661389
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。