裁剪矩形

[编程题]裁剪矩形

热度指数：1128 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

我们每次从大矩形上切下一块，每次切分必须保证是横着一刀两半或竖着一刀两半，且切下来的那一块是小矩形的一种，
求最多能切几块？

示例1

输入

3,5,[[3 ,1],[4,1],[2,2],[2,2]]

输出

备注:

小矩形无方向要求，不可用边角料拼凑小矩形，同种小矩形可以裁剪多个，数据保证0<裁剪出的小矩形个数<=10，0<大矩形长宽，小矩形长宽<=1000且都是整数

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param L int整型 给定布料的长
     * @param W int整型 给定布料的宽
     * @param clothSize int整型vector<vector<>> 依次列举每件衣服所需的长和宽
     * @return int整型
     */
    int dp[1003][1003]={0};
    int clothNumber(int L, int W, vector<vector<int> >& clothSize) {
        if(dp[L][W]!=0)
            return dp[L][W];
        int Max=0;
        if(L < W)
           swap(L, W);
        for(auto &x: clothSize){
            int l=max(x[0], x[1]), w=min(x[0], x[1]), t, a, b;
            if(l<=max(L,W) && w<=min(L,W)){
                if(w<=L && l<=W)
                    swap(l,w);
                t = (L/l) * (W/w);
                a = clothNumber(L, W%w, clothSize) + clothNumber(L%l, W-W%w, clothSize);
                b = clothNumber(L%l, W, clothSize) + clothNumber(L-L%l, W%w, clothSize);
                t += max(a, b);
                Max = max(Max, t);
            }
        }
        dp[L][W] = Max;
        return Max;
    }
};

发表于 2020-08-12 01:09:33 回复(0)

杭电5餐厨师长

这道题目类似于完全背包问题。只不过从一维的钱包变成了二维的体积。

先考虑单次的问题。如果要从长为L，宽为W的矩形中剪一个长为l，宽为w的矩形。那么存在两种情况。

要么是大矩形的长度里-l，宽度W-w。

要么是大矩形里的长度-w，宽度-l。

每种情况都会留下一个不规则的图形。对于这个不规则的图形，经过拆分，又可以把它分成两个完整的小矩形，就又可以使用之前的结果。

使用DP。DP[i][j]表示长度为i,宽度为j的矩形的切割情况。

发表于 2020-03-13 18:39:26 回复(0)

嗯学

这题感觉有点问题，可以参考leetcode的这道题 https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/

像上面这种的切法好像就不是那种规整的切法，是螺旋形的切法(比如切完右下角的6x6之后，剩余的部分并不是分成了两个矩形去填)，上面这个题求的是最少要用几个正方形铺满一个矩形，本题求的是最多，感觉是同样的道理。虽然我写的解法只考虑到了竖着切两半或横着切两半也过了，但是leetcode那道题用同样的思路就过不了（不过周赛的时候有人用这种二维dp解法加上特判一些特殊用例作弊通过了）。

另外贴一下我的代码，代码利用了一个优化，就是分割点一定是所需布料的长或者宽，所以把所有可能的长或者宽统计一下，方便分割时候用。如果不这样，直接按1,2,3,4...这种连续的长度分割会超时。虽然这个代码通过了，鉴于leetcode那道题，但是我有点怀疑这个是不是正确的。。。

class Solution {
public:
    /**
     * 
     * @param L int整型 给定布料的长
     * @param W int整型 给定布料的宽
     * @param clothSize int整型vector<vector<>> 依次列举每件衣服所需的长和宽
     * @return int整型
     */

    int clothNumber(int L, int W, vector<vector<int> >& clothSize) {
        // write code here
        vector<vector<int>> dp(L+1, vector<int>(W+1));
        vector<int>a;
        for(int i = 0; i < clothSize.size(); ++i){
            int l = clothSize[i][0], w = clothSize[i][1];
            a.push_back(l);
            a.push_back(w);
            if(l <= L && w <= W) dp[l][w] = 1;
            if(l <= W && w <= L) dp[w][l] = 1;
        }
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        for(int i = 1; i <= L; ++i)
            for(int j = 1; j <= W; ++j){
                for(auto k : a) if(k <= j) dp[i][j] = max(dp[i][j], dp[i][k]+dp[i][j-k]);else break;
                for(auto k : a) if(k <= i) dp[i][j] = max(dp[i][j], dp[i-k][j]+dp[k][j]);else break;
            }
        return dp[L][W];
    }
};

编辑于 2020-03-13 23:54:30 回复(1)