这是一个创建于 1614 天前的主题，其中的信息可能已经有所发展或是发生改变。
刚才看到的，小学数学题？
10mx10m 的正方形 (1000cm x 1000cm)
7cmx5cm 的长方形
最多可以分成多少个？
如果用计算机编程，怎么解决？
dp? 好像要用到图论......
 | 1 Jooooooooo 2021-07-02 20:20:05 +08:00 想了一下不知道怎么证明小长方形斜着放"不好". |
 | 2 yazoox OP @Jooooooooo 要不，规定不能斜着放吧 |
 | 3 pcbl 2021-07-02 20:28:28 +08:00 200*140? |
 | 4 ynyounuo 2021-07-02 20:30:45 +08:00 我感觉 n × n 的正方形能放多少 a × b 的长方形（ n >> a, n >> b, a ≠ b ）的问题应该不是 polynomial time 可解的 当然个体例子应该可以 |
 | 5 thunderw 2021-07-02 20:32:07 +08:00 如果不用写斜着放的话，横放竖放排列组合？ 横放一行、两行，依次试一下， 剩下的竖着放 --- --- ||||| 要是允许斜着放就不好办了。 /// \\\ 也行 |
 | 6 FurN1 2021-07-02 21:01:19 +08:00 via iPhone dp 听起来是对的方向…… |
 | 7 oott123 2021-07-02 21:41:57 +08:00  1 切成 1x1 的然后拼起来……？这样比较小学数学一点 |
 | 8 Muninn 2021-07-02 22:49:45 +08:00 这感觉不小学啊 |
 | 9 gwy15 2021-07-02 22:50:04 +08:00 1 https://en.wikipedia.org/wiki/Rectangle_packing 里面的第一篇引用讨论了一个排列算法，但是只允许旋转 90 度，有的情况下允许任意旋转是可以达到更优的排列的，比如 11x11 的平面排 4x4 的正方形，用 +0+ 0x0 +0+ |
 | 10 bwangel 2021-07-02 22:55:17 +08:00 横铺 200 * 140 共 28000 个 竖铺 14 * 4 共 56 个 这样一共可以铺 28056 个，剩余面积 40 cm^2 |
 | 11 clockwise9 2021-07-03 01:27:31 +08:00 via Android 如果允许裁剪再拼接的话，是不是只要考虑面积就行了 |
 | 12 Elethom 2021-07-03 07:24:18 +08:00 via iPhone 外星小学？ |
 | 13 oneforallsoft 2021-07-03 10:19:15 +08:00 |
 | 14 wayne233 2021-07-03 11:23:58 +08:00 竖铺 140 排 200 列，共 28000 个，余 20 x 1000 空间； 横铺 4 排 140 列，共 560 个，余 20 x 20 空间； 20 x 20 空间目前能想到可以放置 10 个，余 50cm 即：总共放置 28570 个小矩形，余 50cm |
| 15 bwangel 2021-07-03 12:57:09 +08:00 @oneforallsoft #10 的答案我写错了 横铺 200 * 140 共 28000 个 竖铺 142 * 4 共 568 个 这样一共可以铺 28568 个，剩余面积 6*20 = 120 平方厘米 |
Select Language