文档章节

堆箱子

一贱书生
 一贱书生
发布于 2016/11/23 08:55
字数 779
阅读 6
收藏 0
点赞 0
评论 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
博文 722
码字总数 600072
作品 0
glibc的malloc--更多的改进

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

晨曦之光 ⋅ 2012/04/10 ⋅ 0

堆和栈的区别 之 数据结构和内存

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

langb2014 ⋅ 02/26 ⋅ 0

C语言中堆和栈的区别

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

u014572382 ⋅ 2016/03/24 ⋅ 0

序关系计数问题

这题以前做过,印象还是挺深刻的。 如果我们把不同的变量看成是不同的小球,如果两个变量相等的话,那么对应的小球就在同一个箱子里(箱子们有序地排成一行)。那么,原问题就等价于: 将n个...

m2012 ⋅ 2012/05/20 ⋅ 0

箱排序(Bin Sort)

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

野渡书生 ⋅ 2016/05/03 ⋅ 0

纯C写的小游戏-----最炫酷推箱子

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

小辰GG ⋅ 2017/12/24 ⋅ 0

HDU 1254 推箱子(广搜+优先队列)

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

qq920444182 ⋅ 2017/11/21 ⋅ 0

笨兔兔的故事——带你了解Ubuntu,了解Linux 第八章 碎片

(8)碎片   笨兔兔老师第一讲:什么是磁盘碎片 同学们都坐好啦,都把手机铃声关了,小灵通调成震动,BP机直接扔了——台都没了你还留着它干嘛。好,上课了,首先说说什么叫磁盘碎片。磁盘,...

雨中人X ⋅ 2016/01/04 ⋅ 0

常见逻辑题

1、A、B两人分别在两座岛上。B生病了,A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东西,但东西只能放在箱子里。只要箱子没被上锁,C都会偷走箱子里的东西,不管箱...

翼动动空 ⋅ 2016/05/09 ⋅ 0

面经-智力题

今天连续两面百度,发现有些智力题没有答的比较好。今天脑补了一波智力题大家共同学习一下。 考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放...

此鱼不得水 ⋅ 2016/03/28 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

BS与CS的联系与区别【简】

C/S是Client/Server的缩写。服务器通常采用高性能的PC、工作站或小型机,并采用大型数据库系统,如Oracle、Sybase、InFORMix或 SQL Server。客户端需要安装专用的客户端软件。 B/S是Brower/...

anlve ⋅ 39分钟前 ⋅ 0

发生了什么?Linus 又发怒了?

在一个 Linux 内核 4.18-rc1 的 Pull Request 中,开发者 Andy Shevchenko 表示其在对设备属性框架进行更新时,移除了 union 别名,这引发了 Linus 的暴怒。 这一次 Linus Torvalds 发怒的原...

问题终结者 ⋅ 59分钟前 ⋅ 0

在树莓派上搭建一个maven仓库

在树莓派上搭建一个maven仓库 20180618 lambo init 项目说明 家里有台树莓派性能太慢。想搭建一个maven私服, 使用nexus或者 jfrog-artifactory 运行的够呛。怎么办呢,手写一个吧.所在这个...

林小宝 ⋅ 今天 ⋅ 0

Spring发展历程总结

转自与 https://www.cnblogs.com/RunForLove/p/4641672.html 目前很多公司的架构,从Struts2迁移到了SpringMVC。你有想过为什么不使用Servlet+JSP来构建Java web项目,而是采用SpringMVC呢?...

onedotdot ⋅ 今天 ⋅ 0

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 今天 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 今天 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 今天 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 今天 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部