演算法作業四 - 裝箱問題 (2015/05/31)

box.cpp

#include<iostream>
#include<cstdlib>

using namespace std;

struct Box {
    int side[3], cap=0;
};

int sortnum(int tmp[])
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(tmp[i]>tmp[j])
                swap(tmp[i], tmp[j]);
}

int sortbox (const void * a, const void * b)
{
    Box *boxa = (Box*) a, *boxb = (Box*) b;
    return (boxa->side[0] - boxb->side[0]);
}

bool canIn(const Box a, const Box b) {
    for(int i=0;i<3;i++)
        if(a.side[i] < b.side[i]) continue;
        else return false;
    return true;
}

int main()
{
    int N;
    Box box[1001] = {};

    cin >> N;
    for(int i=0;i<N;i++)
    {
        int tmp[3];
        for (int j=0 ; j<3 ; j++)
            cin >> box[i].side[j];

        sortnum (box[i].side);
    }

    qsort(box, N, sizeof(Box), sortbox);

    for( int i=0 ; i<N ; i++ )    // 每個 box 拿出來比
    {
        int max_cap = 0;
        for( int j=0 ; j<N ; j++ )    // 和其他比
        {
            if(i == j) continue;

            if( canIn(box[j], box[i]) ) // i 是否放得進 j
                max_cap = (!max_cap)?
                1 : (
                        ( box[j].cap != 0 && max_cap < box[j].cap + 1 )?
                            box[j].cap + 1 : max_cap
                    );
        }
        box[i].cap = max_cap;
    }

    int max_cap =0;
    for(int i=0;i<N;i++)
        max_cap = (max_cap<box[i].cap)?
            box[i].cap:max_cap;

    cout << max_cap+1 << endl;

    return 0;
}