堆箱子
堆箱子
一贱书生 发表于1年前
堆箱子
  • 发表于 1年前
  • 阅读 6
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

/**
 * 功能:给你一堆n个箱子,箱子宽wi,高hi,深di。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。
 * 实现方法:搭出最高的一堆箱子,箱子堆的高度为每个箱子高度的总和。

 */

 

两种方法:

方法一:递归法

 

[java] view plain copy

 

  1. //递归法  
  2. public static ArrayList<Box> createStackR(Box[] boxes,Box bottom){  
  3.     int maxHeight=0;  
  4.     ArrayList<Box> maxStack=null;  
  5.       
  6.     for(int i=0;i<boxes.length;i++){  
  7.         if(boxes[i].canBeAbove(bottom)){  
  8.             ArrayList<Box> newStack=createStackR(boxes,boxes[i]);  
  9.             int newHeight=stackHeight(newStack);  
  10.               
  11.             if(newHeight>maxHeight){  
  12.                 maxHeight=newHeight;  
  13.                 maxStack=newStack;  
  14.             }  
  15.         }  
  16.     }  
  17.       
  18.     if(maxStack==null)  
  19.         maxStack=new ArrayList<Box>();  
  20.       
  21.     if(bottom!=null)  
  22.         maxStack.add(0,bottom);  
  23.       
  24.     return maxStack;  
  25. }  
  26.   
  27. public static int stackHeight(ArrayList<Box> stack){  
  28.     int height=0;         
  29.     for(int i=0;i<stack.size();i++){  
  30.         height+=stack.get(i).heigth;  
  31.     }         
  32.     return height;  
  33. }  


 

 

方法二:动态规划

[java] view plain copy

 

  1. //动态规划  
  2. public static ArrayList<Box> createStackDP(Box[] boxes,Box bottem,HashMap<Box,ArrayList<Box>> stackMap){  
  3.     if(bottem!=null&&stackMap.containsKey(bottem))  
  4.         return stackMap.get(bottem);  
  5.       
  6.     int maxHeight=0;  
  7.     ArrayList<Box> maxStack=null;  
  8.       
  9.     for(int i=0;i<boxes.length;i++){  
  10.         if(boxes[i].canBeAbove(bottem)){  
  11.             ArrayList<Box> newStack=createStackDP(boxes, boxes[i], stackMap);  
  12.             int newHeight=stackHeight(newStack);  
  13.               
  14.             if(newHeight>maxHeight){  
  15.                 maxStack=newStack;  
  16.                 maxHeight=newHeight;  
  17.             }  
  18.         }  
  19.     }  
  20.       
  21.     if(maxStack==null)  
  22.         maxStack=new ArrayList<Box>();  
  23.     if(bottem!=null)  
  24.         maxStack.add(0, bottem);  
  25.     stackMap.put(bottem, maxStack);  
  26.       
  27.     /** 
  28.      * 方法clone()来自Object类,其方法签名如下:重写方法时,可以调整参数,但不得改动返回类型。 
  29.      * 因此,如果继承自Object的类重写了clone()方法,它的clone()方法仍将返回Object实例。因此必须转型返回值。 
  30.      */  
  31.       
  32.     return (ArrayList<Box>) maxStack.clone();//返回副本     
  33. }  
  34.   
  35. lt;pre name="code" class="java"><pre name="code" class="java"> public static int stackHeight(ArrayList<Box> stack){  
  36.     int height=0;         
  37.     for(int i=0;i<stack.size();i++){  
  38.         height+=stack.get(i).heigth;  
  39.     }         
  40.     return height;  
  41. }  

 

箱子

 

  1. class Box{  
  2.     int width;  
  3.     int heigth;  
  4.     int depth;  
  5.       
  6.     public Box(int width,int heigth,int depth){  
  7.         this.width=width;  
  8.         this.heigth=heigth;  
  9.         this.depth=depth;  
  10.     }  
  11.       
  12.     public boolean canBeAbove(Box box){  
  13.         if(box.width>this.width&&box.heigth>this.heigth&&box.depth>this.depth)  
  14.             return true;      
  15.         return false;  
  16.     }  
  17. }

或者:

分析:用递归,子问题为以某一个箱子为底的高度最高的塔,确定底后,找到一个可以放在底上的箱子,再递归求解子问题。

注意:存在重复子问题,考虑用动态规划,用表记录中间结果,以便之后查询。

 

[java] view plain copy

在CODE上查看代码片派生到我的代码片

  1. package cci;  
  2.   
  3. import java.util.ArrayList;  
  4.   
  5. class Box{  
  6.     int height;  
  7.     int width;  
  8.     int depth;  
  9.     public Box(int height, int width, int depth){  
  10.         this.height=height;  
  11.         this.width=width;  
  12.         this.depth = depth;  
  13.     }  
  14.     public boolean canBeAbove(Box box){  
  15.         if(box==null)  
  16.             return true;  
  17.         if(height<box.height && width<box.width && depth<box.depth)  
  18.             return true;  
  19.         return false;  
  20.     }     
  21.     public void print(){  
  22.         System.out.println(height+" "+width+" "+depth);  
  23.     }  
  24. }  
  25.   
  26. public class CCI_9_10 {  
  27.       
  28.     public static ArrayList<Box> maxBoxTower(Box[] boxes){  
  29.         return maxBoxTower(boxes, null);  
  30.     }  
  31.     private static ArrayList<Box> maxBoxTower(Box[] boxes, Box bottom){  
  32.         ArrayList<Box> maxTower = new ArrayList<Box>();  
  33.         int maxHeight = 0;  
  34.         //尝试每一个箱子  
  35.         for(int i=0; i<boxes.length; i++){  
  36.             //找到可以放在bottom上的箱子  
  37.             if(boxes[i].canBeAbove(bottom)){  
  38.                 //以找到的箱子为底求解子问题(注意,这里的子问题会被重复求解,提高效率的办法是动态规划)  
  39.                 ArrayList<Box> newTower = maxBoxTower(boxes, boxes[i]);  
  40.                 //利用子问题的解构造当前问题的解  
  41.                 int newHeight = calTowerHeight(newTower);  
  42.                 if(newHeight>maxHeight){  
  43.                     maxHeight = newHeight;  
  44.                     maxTower = newTower;//以boxes[i]为底的最高塔  
  45.                 }  
  46.             }  
  47.         }  
  48.         if(bottom != null){  
  49.             maxTower.add(0, bottom);  
  50.         }  
  51.         return maxTower;  
  52.     }  
  53.     private static int calTowerHeight(ArrayList<Box> tower){  
  54.         int height=0;  
  55.         for(Box box : tower){  
  56.             height += box.height;  
  57.         }  
  58.         return height;  
  59.     }  
  60.       
  61.       
  62.   
  63.     public static void main(String[] args) {  
  64.         // TODO Auto-generated method stub  
  65.         Box[] boxes = new Box[3];  
  66.         boxes[0] = new Box(1,1,1);  
  67.         boxes[1] = new Box(2,2,2);  
  68.         boxes[2] = new Box(3,3,3);  
  69.         ArrayList<Box> result = maxBoxTower(boxes);  
  70.         for(Box item : result){  
  71.             item.print();  
  72.         }  
  73.     }  
  74. }
共有 人打赏支持
粉丝 15
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: