2

给定一个大小为 n 的集合 S，它被划分为大小为 n1,..,nk 的类 (s1,..,sk)。自然地，它认为 n = n1+...+nk。

我有兴趣找出可以组合此分区元素的方法的数量，以便每个组合恰好包含每个类的一个元素。

因为我可以从 s1 中选择 n1 个元素，从 s2 中选择 n2 个元素，依此类推，所以我正在为任意 n1,..nk 寻找 max(n1*..*nk) 的解决方案，它持有 n1+..+nk =n。

我感觉这是一个线性优化问题，但是自从我作为本科生学习这些东西以来已经太久了。我希望有人记得如何计算这个。

4

2 回答 2

3

您正在寻找每个分区中包含一个元素的组合数量？

这只是 n1*n2*...*nk。

编辑：您似乎还问了一个单独的问题：

给定 N，我如何分配 n1, n2, ..., nk 以使它们的乘积最大化。这实际上不是线性优化问题，因为您的变量是相乘的。

它可以通过一些微积分来解决，即通过使用拉格朗日乘数对每个变量进行偏导数，并带有约束。

结果将是 n1 .. nk 应该尽可能接近相同的大小。

if n is a multiple of k, then n_1 = n_2 = ... = n_k = n/k

otherwise, n_1 = n_2 = ... = n_j = Ceiling[n/k]
      and  n_j+1 = ... = n_k = floor[n/k]

基本上，我们尝试将元素尽可能均匀地分配到分区中。如果他们平均分配，那就太好了。如果不是，我们尽可能均匀地划分，剩下的部分，我们给第一个分区每个额外的元素。（不必是第一个分区，这个选择相当随意。）这样，任何两个分区拥有的元素数量的差异最多为一个。

血腥细节：

这是我们希望最大化的乘积函数：

P = n1*n2*...nK

我们使用拉格朗日乘数定义一个新函数：

Lambda = P + l(N - n1 - n2 ... -nk)

并在每个 k n_i 变量中取偏导数：

dLambda/dn_i = P/n_i - l

在 l 中：

dLambda/dl = N - n1 -n2 ... -nk

设置所有偏导数 = 0，我们得到一个由 k + 1 个方程组成的系统，当我们求解它们时，我们将得到 n1 = n2 = ... = nk

一些有用的链接：

拉格朗日乘数

优化

于 2009-02-27T22:40:50.460 回答
2 
floor(n/k)^(k - n mod k)*ceil(n/k)^(n mod k)

——马库斯

PS 对于您给出的 S = {1,2,3,4}, n = 4, k = 2 的示例，这给出：

floor(4/2)^(2 - 4 mod 2)*ceil(4/2)^(4 mod 2)
floor(2)^(2 - 0)*ceil(2)^(0)
2^2 * 2^0
4 * 1
4

……如你所愿。

为了澄清，这个公式给出了分区产生的排列数，其中排列的最大可能数。当然会有其他不太理想的分区。

对于给定的周长，面积最大的矩形是最接近正方形的矩形（在更高维度上也是如此），这意味着您希望边的长度尽可能接近相等（例如，所有平均长度向上或向下四舍五入）。那么公式可以看成是：

   (length of short sides)^(number of short sides)
times
   (length of long sides)^(number of long sides)

这只是满足此约束的超矩形的体积。

请注意，以这种方式查看时，它还告诉您如何构造最大分区。

于 2009-02-27T23:04:51.993 回答