careercup-귀속과 동적 기획 9.10

4551 단어 동적 기획
9.10 n개의 상자를 한 무더기 드릴게요. 상자의 넓이 w, 높이 h, 깊이 d.상자는 뒤집을 수 없으며, 상자를 쌓을 때, 아래 상자의 너비, 높이, 깊이는 반드시 위의 상자보다 커야 한다.하나의 방법을 실현하여 가장 높은 한 무더기의 상자를 만들어 상자의 높이가 각 상자의 높이의 총계이다.
해법:
이 문제를 해결하려면, 우리는 서로 다른 하위 문제 간의 관계를 찾아야 한다.
가령 우리가 또 다음과 같은 상자를 가정한다면: b1, b2,......bn.쌓을 수 있는 가장 높은 상자 더미의 높이는 max(밑부분은 b1의 가장 높은 상자 더미, 밑부분은 b2의 가장 높은 상자 더미,..., 밑부분은bn의 가장 높은 상자 더미)와 같다.상자 하나하나를 상자 더미 밑부분으로 사용해 가능한 최고 높이를 맞추어 보면 상자 쌍의 최고 높이를 찾을 수 있다는 것이다.
소급적 실현 방법:
#include<iostream>

#include<vector>

using namespace std;



struct box

{

    int height;

    int wide;

    int depth;

    box(int h,int w,int d):height(h),wide(w),depth(d) {}

};



bool isValid(vector<box> &path,box b)

{

    if(path.empty())

        return true;

    box top=path[path.size()-1];

    return b.depth<top.depth&&b.height<top.height&&b.wide<top.wide;

}



void helper(vector<box> &boxes,vector<box> &path,int &maxHeight)

{

    int i;

    for(i=0;i<boxes.size(); i++)

    {

        if(isValid(path,boxes[i]))

        {

            path.push_back(boxes[i]);

            helper(boxes,path,maxHeight);

            path.pop_back();

        }

    }

    if(i==boxes.size())

    {

        int j,sum=0;

        for(j=0; j<path.size(); j++)

        {

            sum+=path[j].height;

        }

        if(sum>maxHeight)

            maxHeight=sum;

        return;

    }

}

int maxBoxTower(vector<box> &boxes)

{

    vector<box> path;

    int maxHeight=0;

    helper(boxes,path,maxHeight);

    return maxHeight;

}



int main()

{

    vector<box> b= {box(2,2,2),box(1,2,1),box(3,2,1),box(3,3,3)};

    cout<<maxBoxTower(b)<<endl;

}

좋은 웹페이지 즐겨찾기