[DP] 상자 쌓기 문제

한 무더기의 상자를 주고 각 상자의 세 둘레(길이와 너비)를 알아야 한다. 상자의 정면이 너를 향하고 회전해서 놓을 수 없다. 큰 것은 작은 아래에 놓는 원칙에 따라 쌓아야 한다. 반드시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에서 box1, 이미 바닥으로 사용되었기 때문에 옮겨다닐 때 박스를 뛰어넘어야 한다1, 그러나 이렇게 하면 문제의 복잡성을 크게 증가시킬 수 있다.
다행히 이 문제는 특별한 점이 있다. strictly better, 만약box1 이미 밑에 있습니다. 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;

    }

}