刚才看到的,小学数学题?
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
IgniteWhite 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 平方厘米 |