裁剪矩形

[编程题]裁剪矩形

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

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

示例1

输入

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

输出

备注:

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

算法知识视频讲解

Miss.Zhou

发表于 2020-02-07 13:54:13

二维完全背包套用完全背包的想法：外层循环是体积，内层循环是种类无非就是外面再加一层而已也没办法状态压缩，因为不知道%多少 class Solution { public: /** * * @param L int整型给定布料的长 * @param W i 展开全文

ls.joshua

发表于 2020-04-07 14:30:21

joshua分享：首先该类问题是典型的完全背包问题，现在考虑裁剪的时候，需要考虑对现有的布料进行横向裁剪还是是竖向裁剪，每一种裁剪方法都有两种分割方法，两种裁剪方法一共有四种状态，所以每一款衣服的每一种裁剪都有四种状态选择，然后遍历所有的款式就可以了 class Solution { public: 展开全文