牛妹的衣服 题解

二维完全背包

套用完全背包的想法：

外层循环是体积，内层循环是种类

无非就是外面再加一层而已
也没办法状态压缩，因为不知道%多少

class Solution {
public:
    /**
     *
     * @param L int整型 给定布料的长
     * @param W int整型 给定布料的宽
     * @param clothSize int整型vector<vector<>> 每件衣服所需的尺寸
     * @return int整型
     */
    int max(int a,int b,int c)
    {
        if(a>b)
        {
            if(c>a) return c;
            return a;
        }
        if(c>b) return c;
        return b;
    }
    int clothNumber(int L, int W, vector<vector<int> >& clothSize) {
        // write code here
        int dp[1005][1005];
        int n = clothSize.size();
        if (n == 0) return 0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=L;i++)
        {//类似于背包问题中枚举容量的状态
            for(int j=0;j<=W;j++)
            {
                for(int k=0;k<n;k++)
                {//类似于背包问题终枚举物品的状态
                    if(i >= clothSize[k][0] && j >= clothSize[k][1])
                    {//(1)图片解释
                        dp[i][j] = max(dp[i][j],
                                     dp[i - clothSize[k][0]][j] + dp[clothSize[k][0]][j - clothSize[k][1]] + 1,
                                     dp[i][j - clothSize[k][1]] + dp[i - clothSize[k][0]][clothSize[k][1]] + 1);
                    }
                    if(i >= clothSize[k][1] && j >= clothSize[k][0])
                    {//（2）图片解释
                        dp[i][j] = max(dp[i][j],
                                     dp[i - clothSize[k][1]][j] + dp[clothSize[k][1]][j - clothSize[k][0]] + 1,
                                     dp[i][j - clothSize[k][0]] + dp[i - clothSize[k][1]][clothSize[k][0]] + 1);
                    }

                }
            }
        }
        return dp[L][W];
    }
};

（1）图片解释

（2）图片解释

分别按着这两种虚线裁剪布料的转移方程
贪心应该做不了，首先如果用面积贪心，肯定行不通。因为裁剪我需要知道具体裁剪的长和宽， 以及裁剪时长和宽的方向。光用贪心，不能够穷举所有的状态。