将巧克力棒分成相等部分的算法

Question

一个随意的想法突然出现在我的脑海里(当然我正在分享巧克力吧!).我想知道是否有一个通用的算法来解决这个问题.

问题是这样的:

信息

1.你有一个巧克力棒,小方块排列成矩形矩阵
2.房间里有n个人

问题

编写一个输出最佳配置(pxq)的算法,其中可以在n, n-1, n-2...., 2, 1给定以下限制的人之间平均分配条:

1.小方块(单位正方形)不能切成小块
2.所有中断都必须是完全沿着一个轴
3 完成.中断的总数不能超过n(这是为了阻止低效的解决方案,例如试图将整个条分成小块并分割小块)
4.p或q不能相等1. yx在其中一个答案中指出,如果一方有一个酒吧,问题很容易解决.然而,这对于现实世界的情况来说不是一个好的解决方案 - 这是解决这个问题的意图:)

示例

对于n = 4,最佳配置是4 x 3.

 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~

这种配置可以分为:

沿垂直轴
3 个断裂的4个人3 个沿水平轴有2个断裂的人2个
中间有1个断裂的人

其他经验解决方案(n, p, q) = (1, 1, 1); (2, 2, 1); (3, 3, 2); (4, 4, 3); (5, 5, 12); (6, 6, 10) OR (6, 5, 12)

澄清
断裂定义为沿一个轴的切口如果适用,条形的子集.为了更好地说明这一点,假设你有一个像这样的2 x 2巧克力棒:

 ~~~~ ~~~~
|    |    |
 ~~~~ ~~~~
|    |    |
 ~~~~ ~~~~

传统智慧说你需要做2次断裂(中间向下和横向的垂直轴)将这个条分成4个.然而,在现实世界中(如果它是巧克力棒),你首先将它分成两半,然后再分别打破每一半.这使得总共有3个休息时间 - 整个酒吧有1个休息时间,并且酒吧的2个不同子集上有2个休息时间.

我无法在互联网上的任何地方找到解决方案 - 如果有人认为这不是编程相关的问题或解决方案已经存在,请随时关闭问题=)

Answer 1

在我看来,你正在寻找可以被1和n之间的所有数字均匀分割的数字.这被称为1,...,n的最小公倍数.根据定义,包含1,...,n个正方形的最小公倍数的正方形可以均匀地分成尺寸为1,...,n的块.您正在寻找最多n个分裂,这会增加问题的复杂性,这可能是也可能是不可能的.

你的n = 4的例子是LCM(4,3,2,1),即12.LCM(5,4,3,2,1)是60. LCM(6,5,4,3,2,1) )也是60.

它们总是可以布置为1xLCM(n,...,1)矩形,并且总是可以分成1,......,n甚至成n-1或更少的分段.

例如,当n = 4时,LCM(4,3,2,1)= 12.矩形是

############

并可分为以下几种:

1: ############     // 0 cuts
2: ###### ######    // 1 cut
3: #### #### ####   // 2 cuts
4: ### ### ### ###  // 3 cuts (3 being n-1)