[itint5]堆放积木 - 阿牧遥 - 博客园

[itint5]堆放积木 - 阿牧遥 - 博客园

http://lixinzhang.github.io/itint5-mian-shi-ti-zong-jie.html
有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。

 积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。

 样例：

 有7个积木boxes:

    [(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]

 最多可以搭6个积木，从上到下分别为：

    (56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)

 所以函数应该返回6。

 题目来源：CRACKING THE CODING INTERVIEW 9.7

排序 + DP 按一个维度排序，然后最长不降递增子序列。

先按照一维排序，然后在第二维求最大上升子序列。注意比较的时候还要考虑第一维虽然排序，还是有可能相等的。

https://github.com/AnnieKim/ITint5/blob/master/034_%E5%A0%86%E6%94%BE%E7%A7%AF%E6%9C%A8.cpp

 Solution: 先按照vol进行排序，题目就变成了根据weight寻找最长严格递增子序列。

int mycompare(Box a, Box b) {

    if (a.vol == b.vol)

        return a.weight < b.weight;

    return a.vol < b.vol;

}

int maxBoxes(vector<Box> &boxes) {

    int N = boxes.size();

    if (N == 0) return 0;

    sort(boxes.begin(), boxes.end(), mycompare);

    int dp[N];

    int res = 1;

    for (int i = 0; i < N; ++i)

    {

        dp[i] = 1;

        for (int j = 0; j < i; ++j)

            if (boxes[i].vol > boxes[j].vol && boxes[i].weight > boxes[j].weight)

                dp[i] = max(dp[i], dp[j] + 1);

        res = max(res, dp[i]);

    }

    return res;

}

bool comp(const Box &a, const Box &b) {

    if (a.vol != b.vol) {

        return a.vol < b.vol;

    } else {

        return a.weight < b.weight;

    }

}

 

/*积木的定义(请不要在代码中定义该结构)

struct Box {

  int vol, weight;

};*/

int maxBoxes(vector<Box> &boxes) {

    sort(boxes.begin(), boxes.end(), comp);

    int size = boxes.size();

    int max = 0;

    vector<int> dp(size);

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

        dp[i] = 0;

        for (int j = 0; j < i; j++) {

            if (boxes[j].weight < boxes[i].weight

               &&boxes[j].vol < boxes[i].vol) {

                if (dp[j] > dp[i]) dp[i] = dp[j];

            }

        }

        dp[i]++;

        if (dp[i] > max) max = dp[i];

    }

    return max;

}

/*积木的定义(请不要在代码中定义该结构)
struct Box {
  int vol, weight;
};*/

bool cmp(Box b1, Box b2){
    return b1.vol < b2.vol;
}

bool isvalid(Box & b1, Box & b2){
    return (b1.weight > b2.weight) 
        && (b1.vol > b2.vol);
}

int maxBoxes(vector<Box> &boxes) {
    if(boxes.size() <=1 ) return boxes.size();
    sort(boxes.begin(), boxes.end(), cmp);
    vector<int> f(boxes.size(), 1);
    f[0] = 1;
    int res = 1;
    for(int i=1; i<f.size(); i++){ 
        for(int j=0; j<i; j++){
            f[i] = max(f[i], isvalid(boxes[i], boxes[j]) ? f[j]+1 : 0);
        }
        res = max(res, f[i]);
    }
    return res;
}

Read full article from [itint5]堆放积木 - 阿牧遥 - 博客园