文档章节

堆箱子

一贱书生
 一贱书生
发布于 2016/11/23 08:55
字数 779
阅读 7
收藏 0

/**
 * 功能:给你一堆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. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
glibc的malloc--更多的改进

前面说过glibc实现了malloc,它实现linux系统的堆管理,在linux中没有专有的所谓的API,所有的调用几乎都以c库为根本,因此glibc显得尤为重要,glibc的实现抛开自己的独特策略不说它和windo...

晨曦之光
2012/04/10
767
0
堆和栈的区别 之 数据结构和内存

数据结构的栈和堆 首先在数据结构上要知道堆栈,尽管我们这么称呼它,但实际上堆栈是两种数据结构:堆和栈。 堆和栈都是一种数据项按序排列的数据结构。 栈就像装数据的桶或箱子 我们先从大家...

langb2014
02/26
0
0
C语言中堆和栈的区别

原文:点击打开链接 在计算机领域,堆栈是一个不容忽视的概念,我们编写的C语言程序基本上都要用到。 但对于很多的初学着来说,堆栈是一个很模糊的概念。堆栈:一种数据结构、一个在程序运 ...

u014572382
2016/03/24
0
0
纯C写的小游戏-----最炫酷推箱子

很多编程爱好者都编写过推箱子游戏编程吧,最近有好些朋友看见我以前的推箱子程序后, 问我是怎么做的。我一直想把这个程序的整个过程写一份详细的东西,与各位编程爱好者分享,一直没空。正...

小辰GG
2017/12/24
0
0
HDU 1254 推箱子(广搜+优先队列)

Problem Description 推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱...

qq920444182
2017/11/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux命令备忘录: jobs 显示Linux中的任务列表及任务状态命令

jobs命令用于显示Linux中的任务列表及任务状态,包括后台运行的任务。该命令可以显示任务号及其对应的进程号。其中,任务号是以普通用户的角度进行的,而进程号则是从系统管理员的角度来看的...

开元中国2015
51分钟前
1
0
springboot Whitelabel Error Page(Not Found)解决方案

当出现上图图的错误时注意 报错信息 There was an unexpected error (type=Not Found, status=404). Not Found代表未访问到资源 解决方案:比较访问路径和代码的路径有没有写错 正确的访问路...

斩神魂
51分钟前
2
0
记一次hbase master停止服务的原因以及恢复

在Hdfs空间不足的情况下,拒绝写入,hbase会down掉。如果hdfs空间没有清理的情况下,重新启动hbase,会报splitlog失败,原因是wal日志重写过程中会写hdfs,写不进去导致的。重启不成功。 解决...

PageYi
55分钟前
1
0
如何从平面设计转行到UI设计?

时代的变迁,科技的进步,工具的发展,薪资的差距,促使许多人转行的原因,但平面与界面两者之间有着哪些的差异呢?如果,想要转行又该具备哪些条件呢? 平面、界面设计之间的差异性 平面设计...

mo311
58分钟前
4
0
线程池整理

一般在生产环境中,我们都不会直接new一个Thread,然后再去start(),因为这么做会不断频繁的创建线程,销毁线程,过大的线程会耗尽CPU和内存资源,大量的垃圾回收,也会给GC带来压力,延长GC停顿时间...

算法之名
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部