首页 > 代码库 > [DP] 堆盒子问题

[DP] 堆盒子问题

2024-07-08 06:04:14   219人阅读

给一堆盒子，知道每个盒子的三围（长宽高），盒子正面朝你，不能旋转摆放，按照大的放在小的下面的原则堆起来，必须是 strictly larger，同样大小的盒子不行，问怎么样堆到最大的高度？

思路：动态规划 

最优解一定是 max( {box_1 be the bottom}, {box_2 be the bottom}, ... , {box_n be the bottom} )，所以我们遍历所有的 box, 把每个box作为底部构建subproblem。

按说在subproblem {box_1 be the bottom}中，box candidates 中不能再有box_1，因为它已经用作底部了，所以遍历的时候理应跳过 box_1，然而这样会大大增加题目的复杂性。

幸好这道题有特殊的地方：strictly better, 如果 box_1 已经是底部了，那么即使它在 candidates 中再次出现也不会被选中，就不会产生问题。

代码：

package chapter9;import java.util.ArrayList;import java.util.HashMap;public class P10_book_ {        public ArrayList<Box> createStack(Box[] boxes){        return createStackR(boxes, null, new HashMap<Box, ArrayList<Box>>());    }        public ArrayList<Box> createStackR(Box[] boxes, Box bottom,             HashMap<Box, ArrayList<Box>> stackMap){                if(stackMap.containsKey(bottom))            return stackMap.get(bottom);                ArrayList<Box> bestStack = new ArrayList<Box>();        int bestHeight = 0;                for(Box b : boxes){            if(b.canBeAbove(bottom)){                ArrayList<Box> newStack = createStackR(boxes, b, stackMap);                int newHeight = stackHeight(newStack);                                if(newHeight > bestHeight){                    bestHeight = newHeight;                    bestStack = newStack;                }            }        }                // make a copy of bestStack before modify it        bestStack = (ArrayList<Box>)bestStack.clone();                if(bottom != null)            bestStack.add(bottom);                stackMap.put(bottom, bestStack);        return bestStack;    }                public int stackHeight(ArrayList<Box> stack){                if(stack == null || stack.isEmpty())            return 0;                int totalHeight = 0;        for(Box b : stack){            totalHeight += b.height;        }        return totalHeight;    }    }class Box{        int width;    int height;    int depth;        public boolean canBeAbove(Box box){        if(box == null)            return true;                if(width < box.width && height < box.height && depth < box.depth){            return true;        }                return false;    }}

 


联系
我们