首页 > 代码库 > 9.10 n个箱子，宽w、高h、深d，箱子不能翻转，下面的箱子的宽度、高度和深度必须大于上面的，实现一个方法，搭出最高的一堆箱子。
9.10 n个箱子，宽w、高h、深d，箱子不能翻转，下面的箱子的宽度、高度和深度必须大于上面的，实现一个方法，搭出最高的一堆箱子。
递归求解，求出已某个箱子为底，返回最高可以放的箱子堆。
DP思想优化，对于已经求过的已某个箱子为底的情况，用一个map记录下来，以后直接返回即可。
注意一些clone等一些语言细节。
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Solution { public ArrayList<Box> maxHeight(Box[] boxes) { Map<Box, ArrayList<Box>> cache = new HashMap<Box, ArrayList<Box>>(); return maxHeight(boxes, null, cache); } private ArrayList<Box> maxHeight(Box[] boxes, Box bottom, Map<Box, ArrayList<Box>> cache) { // 用于实现DP的思想，注意每个返回值要clone一份，否则返回去之后cache中结果也会被外界引用的改变而改变。 if (cache.containsKey(bottom)) return (ArrayList<Box>) cache.get(bottom).clone(); int maxHeight = 0; ArrayList<Box> res = new ArrayList<Box>(); for (int i = 0; i < boxes.length; i++) { if (boxes[i].canAbove(bottom)) { // 递归求解上面的箱子 ArrayList<Box> tmp = maxHeight(boxes, boxes[i], cache); // 计算堆的高度 int curHeight = calcu(tmp); if (curHeight > maxHeight) { curHeight = maxHeight; res = tmp; } } } // 当前箱子加进去 if (bottom != null) res.add(bottom); // 结果放入cache中用于dp cache.put(bottom, res); return res; } private int calcu(List<Box> list) { int res = 0; for (Box each : list) { res += each.h; } return res; } public static void main(String[] args) { Box[] boxes = { new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3) }; System.out.println(new Solution().maxHeight(boxes)); }}class Box { int w; int h; int d; public Box(int w, int h, int d) { this.w = w; this.h = h; this.d = d; } boolean canAbove(Box b) { if (b == null) return true; return w < b.w && h < b.h && d < b.d; } @Override public String toString() { return "Box [w=" + w + ", h=" + h + ", d=" + d + "]"; }}
9.10 n个箱子，宽w、高h、深d，箱子不能翻转，下面的箱子的宽度、高度和深度必须大于上面的，实现一个方法，搭出最高的一堆箱子。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。