刚才看到的，小学数学题？
10mx10m 的正方形 (1000cm x 1000cm)
7cmx5cm 的长方形
最多可以分成多少个？
如果用计算机编程，怎么解决？
dp? 好像要用到图论......
This topic created in 1794 days ago, the information mentioned may be changed or developed.
 |
1
Jooooooooo Jul 2, 2021
想了一下不知道怎么证明小长方形斜着放"不好".
|
 |
2
yazoox OP @Jooooooooo 要不，规定不能斜着放吧
|
 |
3
pcbl Jul 2, 2021
200*140?
|
 |
4
ynyounuo Jul 2, 2021
我感觉 n × n 的正方形能放多少 a × b 的长方形（ n >> a, n >> b, a ≠ b ）的问题应该不是 polynomial time 可解的
当然个体例子应该可以 |
 |
5
thunderw Jul 2, 2021
如果不用写斜着放的话，横放竖放排列组合？
横放一行、两行，依次试一下， 剩下的竖着放 --- --- ||||| 要是允许斜着放就不好办了。 /// \\\ 也行 |
 |
6
FurN1 Jul 2, 2021 via iPhone
dp 听起来是对的方向……
|
 |
7
oott123 Jul 2, 2021  1
切成 1x1 的然后拼起来……？这样比较小学数学一点
|
 |
8
Muninn Jul 2, 2021
这感觉不小学啊
|
 |
9
gwy15 Jul 2, 2021 1
https://en.wikipedia.org/wiki/Rectangle_packing
里面的第一篇引用讨论了一个排列算法，但是只允许旋转 90 度，有的情况下允许任意旋转是可以达到更优的排列的，比如 11x11 的平面排 4x4 的正方形，用 +0+ 0x0 +0+ |
 |
10
bwangel Jul 2, 2021
横铺 200 * 140 共 28000 个
竖铺 14 * 4 共 56 个 这样一共可以铺 28056 个，剩余面积 40 cm^2 |
 |
11
clockwise9 Jul 3, 2021 via Android
如果允许裁剪再拼接的话，是不是只要考虑面积就行了
|
 |
12
Elethom Jul 3, 2021 via iPhone
外星小学？
|
 |
13
oneforallsoft Jul 3, 2021
|
 |
14
LittleSharkDaDa Jul 3, 2021
竖铺 140 排 200 列，共 28000 个，余 20 x 1000 空间；
横铺 4 排 140 列，共 560 个，余 20 x 20 空间； 20 x 20 空间目前能想到可以放置 10 个，余 50cm² 即：总共放置 28570 个小矩形，余 50cm² |
|
15
bwangel Jul 3, 2021
@oneforallsoft
#10 的答案我写错了 横铺 200 * 140 共 28000 个 竖铺 142 * 4 共 568 个 这样一共可以铺 28568 个，剩余面积 6*20 = 120 平方厘米 |
Select Language