时间戳

首页 > 解决方案 > 计算具有 k 个部分的整数部分，每个部分低于某个阈值 m

algorithm - 计算具有 k 个部分的整数部分，每个部分低于某个阈值 m

问题描述

我想计算我们可以将数字划分为不同部分的方法的数量n，k其中每个部分不大于m.

因为k := 2我有以下算法：

public int calcIntegerPartition(int n, int k, int m) {

  int cnt=0;
  for(int i=1; i <= m;i++){
    for(int j=i+1; j <= m; j++){
      if(i+j == n){
        cnt++;
        break;
      }
    }
  }
  return cnt;
}

但是我如何计算整数分区k > 2呢？通常我有n > 100000, k := 40, m < 10000.

先感谢您。

标签： algorithmmathnumberscombinationsinteger-partition

解决方案

让我们从选择 k 个最大的合法数开始：m, m-1, m-2, ..., m-(k-1)。这加起来为 k*m - k(k-1)/2。如果 m < k，则没有解决方案，因为最小分区将 <= 0。假设 m >= k。

假设 p = (k m - k (k-1)/2) - n。

如果 p < 0，则没有解，因为我们可以得出的最大数小于 n。假设 p >= 0。请注意，如果 p = 0，则只有一个解，因此我们假设 p > 0。

现在，假设我们首先选择 k 个最大的不同合法整数，然后我们纠正它以获得解决方案。我们的更正涉及将值向左（在数轴上）移动 1 个插槽，进入空插槽，恰好 p 次。我们有多少种方法可以做到这一点？

开始的最小值是 m-(k-1)，它可以向下移动 1，最多可以移动 mk 次。在此之后，每个连续值都可以向上移动到其前一个移动。

现在的问题是，有多少个最大值为 mk 和 p 的非增整数序列？这就是分区问题。即，我们可以将 p 分区多少种方式（最多分成 k 个分区）。这不是对此的封闭形式的解决方案。

有人已经在这里写了这个问题的一个很好的答案（需要稍微修改以满足您的限制）：

是否有一种有效的算法用于有限数量的整数分区？

推荐阅读