文档章节

堆箱子

一贱书生
 一贱书生
发布于 2016/11/23 08:55
字数 779
阅读 8
收藏 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
863
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

没有更多内容

加载失败,请刷新页面

加载更多

为什么只有你每次提交代码,log里面会出现merge

http://www.cnblogs.com/Sinte-Beuve/p/9195018.html git的merge和rebase https://blog.csdn.net/liuxiaoheng1992/article/details/79108233...

踏破铁鞋无觅处
12分钟前
0
0
如何学习大数据:spark发布程序

一、对于spark程序只是用于默认的spark包的情况 直接点击pcakage 将程序进行在linux当中进行发布 客户端模式:测试 spark-submit --class com.keduox.App \ --master yarn \ --deploy-mode ...

架构师springboot
12分钟前
0
0
oracle job(定时任务)

创建 定时任务 job declare job number;BEGIN DBMS_JOB.SUBMIT( JOB => job, -- job任务的唯一标识(自动生成) WHAT => 'INSERT into TEXTL (id) VALUES(TEXT......

骑羊放狼灬
16分钟前
0
0
Spring声明式事务在抛出异常时不回滚(RollBack)

Spring声明式事务默认只在RuntimeException时Rollback(回滚),不当的try catch会导致事务不回滚。 spring事务默认运行时异常回滚,RuntimeException 配置时添加异常回滚 rollback-for="Th...

叶落花开
17分钟前
0
0
赋能时空云计算 阿里云数据库时空引擎Ganos上线

随着移动互联网、位置感知技术、对地观测技术的快速发展,时空信息已从传统GIS行业渗透到大众应用及各行各业。从静态POI(兴趣点)到APP位置信息,从导航电子地图到车辆行驶轨迹,从卫星影像...

阿里云云栖社区
19分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部