文档章节

堆箱子

一贱书生
 一贱书生
发布于 2016/11/23 08:55
字数 779
阅读 6
收藏 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
箱排序(Bin Sort)

1、基本思想 排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n)。 箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫...

野渡书生
2016/05/03
8
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
1
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0
memcached命令行、memcached数据导出和导入

一、memcached命令行 yum装telnet yum install telent 进入memcached telnet 127.0.0.1 11211 命令最后的2表示,两位字节,30表示过期时间(秒) 查看key1 get key1 删除:ctrl+删除键 二、m...

Zhouliang6
今天
1
0
Linux定时备份MySQL数据库

做项目有时候要备份数据库,手动备份太麻烦,所以找了一下定时备份数据库的方法 Linux里有一个 crontab 命令被用来提交和管理用户的需要周期性执行的任务,就像Windows里的定时任务一样,用这...

月夜中徘徊
今天
1
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部