小学数学题， 100 平方米的正方形可以最多分成多少个 7cm x 5cm 的长方形？

[yazoox]

刚才看到的，小学数学题？

10mx10m 的正方形 (1000cm x 1000cm)

7cmx5cm 的长方形

最多可以分成多少个？

如果用计算机编程，怎么解决？

dp? 好像要用到图论......

[Jooooooooo]

想了一下不知道怎么证明小长方形斜着放"不好".

[yazoox]

@Jooooooooo 要不，规定不能斜着放吧

[pcbl]

200*140?

[ynyounuo]

我感觉 n × n 的正方形能放多少 a × b 的长方形（ n >> a, n >> b, a ≠ b ）的问题应该不是 polynomial time 可解的
当然个体例子应该可以

[thunderw]

如果不用写斜着放的话，横放竖放排列组合？
横放一行、两行，依次试一下，
剩下的竖着放
---
---
|||||

要是允许斜着放就不好办了。
///
\\\
也行

[IgniteWhite]

dp 听起来是对的方向……

[oott123]

切成 1x1 的然后拼起来……？这样比较小学数学一点

[Muninn]

这感觉不小学啊

[gwy15]

https://en.wikipedia.org/wiki/Rectangle_packing

里面的第一篇引用讨论了一个排列算法，但是只允许旋转 90 度，有的情况下允许任意旋转是可以达到更优的排列的，比如 11x11 的平面排 4x4 的正方形，用
+0+
0x0
+0+

[bwangel]

横铺 200 * 140 共 28000 个
竖铺 14 * 4 共 56 个

这样一共可以铺 28056 个，剩余面积 40 cm^2

[clockwise9]

如果允许裁剪再拼接的话，是不是只要考虑面积就行了

[Elethom]

外星小学？

[oneforallsoft]

@bwangel
200 * 142 = 28400
28400 + 142 = 28542
剩余 142 cm^2

[wayne233]

竖铺 140 排 200 列，共 28000 个，余 20 x 1000 空间；
横铺 4 排 140 列，共 560 个，余 20 x 20 空间；
20 x 20 空间目前能想到可以放置 10 个，余 50cm²
即：总共放置 28570 个小矩形，余 50cm²

[bwangel]

@oneforallsoft

#10 的答案我写错了

横铺 200 * 140 共 28000 个
竖铺 142 * 4 共 568 个

这样一共可以铺 28568 个，剩余面积 6*20 = 120 平方厘米

[bwangel]

@bwangel #14

#14 楼的答案对，剩下的 6*20 中，还可以横着放置两个

所以总数量是 28000 + 568 + 2 = 28570 个 剩余面积 1*20 + 6 * 5 = 50 平方厘米

----

由于其他面积都可以被铺满，所以这个问题可以简化成

20 * 20 的正方形里，最多可以放多少个 5 * 7 的矩形

目前找到的答案是 10 个，剩余 50 cm^2 的面积。