12

一个随机的想法突然出现在我的脑海中（当然是在我分享巧克力棒的时候！）。我想知道是否有通用算法来解决这个问题。

问题是这样的：

信息

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

问题编写一个算法，输出最优配置 (pxq)，其中在以下限制

条件下，条形可以在人们之间平均共享： 1. 不能将小方块（单位方块）切割成更小的部分2. 所有休息都必须是完全沿一个轴进行3. 断裂的总数不能超过 n （这是为了阻止低效的解决方案，例如尝试将整个杆分成小块并将小块分成小块）4. p 或 q 不能相等to 1. yx 在其中一个答案中指出，如果一侧有 1 bar，则问题很容易解决。然而，这对于现实世界的情况来说并不是一个好的解决方案——这是解决这个问题的目的:)示例n, n-1, n-2...., 2, 1








对于 n = 4，最佳配置是 4 x 3。

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

这种配置可以分为：

4 人在沿垂直轴的
3 个休息时间 3 人在水平轴上有 2 个休息时间2
人在中间有 1 个休息时间

其他经验解决方案是栏的子集（如果适用）。为了更好地说明这一点，假设您有一个像这样的 2 x 2 巧克力棒：(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 次中断（中间的垂直轴 - 向下和交叉）才能将此条分成 4 块。然而，在现实世界中（如果它是一块巧克力棒），你会先把它分成两半，然后再分别分开每一半。这使得总共 3 次休息 - 1 次休息在整个酒吧和 2 次休息在酒吧的 2 个不同的子组。

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

4

3 回答 3

8

在我看来，您正在寻找可以被 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)
于 2009-05-13T19:50:08.893 回答
3

由于您不能一次切割多件，因此对于您想要的任意数量的件 m，其中 m 在集合 (1..n) 中，您将始终需要 m-1 切割。每次切割都会多制作一件，您从一件开始。

在之前的解决方案的基础上，我认为您正在直观地寻找以下算法：

A = LCM(n)
p = greatest divisor of A <= sqrt(A)
q = A/p

这个算法应该是微不足道的，（例如，从 p = floor(sqrt(A)) 开始并倒计时直到 mod(A,p) == 0）。

您想要 sqrt 的原因是限制您检查的数字数量。毕竟，你总是有一个除数 <= sqrt(A) 和一个 >= sqrt(A)

于 2009-05-14T00:47:55.630 回答
1

回答这个问题的一个好方法是使用广度优先搜索算法。该算法将尝试整个巧克力棒的所有可能断裂。然后对于每个可能的问题状态，尝试所有可能的中断，这将继续，同时跟踪碎片的均匀性。

我想补充一点，规则将强制巧克力棒的哪些休息是合法的，而那些不合法的可能状态会从算法中剔除。

于 2009-05-13T19:41:16.927 回答