将n个对象划分为k个组的方式数量，以使没有一个组比以前形成的组具有更少的对象？

问题描述 投票：2回答：3

示例：n = 8，k = 4答案：5

[1,1,1,5]，[1,1,2,4]，[1,1,3,3]，[1,2,2,3]，[2,2,2,2 ]

[我想到了使用动态编程来计算将8个对象划分为4组的方式的数量，但是不了解如何跟踪上一组中的对象的数量。

DP方法：

for(int j=0;j<=n;j++)
{
    for(int i=1;i<=k;i++)
    {
        if(j<i)
            continue;
        if(j==i)
            dp[j]=1;
        for(int k=1;k<i;k++)
        {
            dp[j]+=dp[k]*dp[j-k];
        }
    }
}

请提供帮助。我对DP比较陌生。

recursion dynamic-programming memoization
3个回答
1
投票

将动态编程（DP）视为一种简单的优化技术，可以加快某些递归过程的速度。如果重复执行递归调用（如斐波那契数词），则存储它们的结果可以大大加快程序的速度。但是底层逻辑仍然是递归调用。因此，让我们首先递归地解决该程序，然后看看可以在何处应用DP优化。

(8, 4)只有五个解决方案，足够小，即使时间在算法上是指数级的，也仍然可以管理。让我们尝试一个简单的递归。首先，让我们实际构建输出而不是对其进行计数，以便再次检查我们在做的事情是否正确。

此版本基于以下思想：我们可以设置列表的第一个数字，将其余元素的最小值记录为该值，然后对剩余位置重复该值。最后，我们以更高的初始编号再试一次。因此，除了我们的n和k输入之外，我们还需要保留一个以min开头的1参数。

这里是一个版本：

const f = (n, k, min = 1) => 
  k < 1 || n < k * min
    ? []
  : k == 1
    ? [[n]]
  : [
      ... f (n - min, k - 1, min) .map (xs => [min, ...xs]), 
      ... f (n, k, min + 1)
    ]

console .log (
  f (8, 4) //~> [[1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3], [2, 2, 2, 2]]
)

（（您未指定语言标签；如果不清楚Javascript ES6语法，我们可以用另一种样式重写。）

由于这似乎是正确的，我们可以编写一个简单的版本只是为了计算结果：

const f = (n, k, min = 1) => 
  k < 1 || n < k * min
    ? 0
  : k == 1
    ? 1
  : f (n - min, k - 1, min) + f (n, k, min + 1)

console .log (
  f (8, 4) //~> 5
)

但是如果我们要尝试更大的集合，例如f（1000，10）（通过检查，应为886745696653253 1），则可能需要一些时间来计算。我们的算法可能是指数的。因此，我们可以通过两种方式进行动态编程。最明显的是bottom-up方法：

const f = (_n, _k, _min = 1) => {
  const cache = {}
  for (let n = 1; n <= _n; n ++) {
    for (let k = 1; k <= Math.min(_k, n); k++) {
      for (let min = n; min >= 0; min--) {
        cache [n] = cache[n] || {}
        cache [n] [k] = cache [n] [k] || {}
        cache [n] [k] [min] = 
          k < 1 || n < k * min
            ? 0
            : k == 1
               ? 1
               : cache [n - min] [k - 1] [min]  + cache [n] [k] [min + 1]
      }
    }
  }
  return cache [_n] [_k] [_min]
}

console.time('time taken')
console .log (
  f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')

如果没有其他原因，那么在此处找出正确的边界是很棘手的，因为递归基于min的增加值。 [很可能我们正在计算沿途不需要的东西。

它也是丑陋的代码，在仅获得性能的同时，失去了原始文档的优雅和可读性。

我们仍然可以通过记住我们的功能来保持优雅；这是top-down方法。通过使用可重用的memoize函数，我们几乎可以完整地使用递归解决方案：

const memoize = (makeKey, fn) => {
  const cache = {}
  return (...args) => {
    const key = makeKey(...args)
    return cache[key] || (cache[key] = fn(...args))
  }
}

const makeKey = (n, k, min) => `${n}-${k}-${min}`        
        
const f = memoize(makeKey, (n, k, min = 1) => 
  k < 1 || n < k * min
    ? 0
  : k == 1
    ? 1
  : f (n - min, k - 1, min)  + f (n, k, min + 1)
)

console.time('time taken')
console .log (
  f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')

memoize将一个在每次调用时计算其结果的函数转换为仅在第一次看到一组特定输入时才对其进行计算的函数。此版本要求您提供一个附加函数，以将参数转换为唯一键。还有其他写方法，但它们有点难看。在这里，我们只需将(8, 4, 1)转换为"8-4-1"，然后将结果存储在该键下。没有歧义。下次我们用(8, 4, 1)调用时，已经计算的结果将立即从缓存中返回。

请注意，有尝试的诱惑

const f = (...args) => {...}
const g = memoize(createKey, f)

但是如果f中的递归调用指向f，则此方法无效。而且，如果他们指向g，我们已经混淆了实现，并且f不再是独立的，因此没有什么理由。因此，我们将其写为memomize(createKey, (...args) => {...})。 offer alternatives的高级技术不在这里讨论的范围。

在自下而上的DP和自上而下的DP之间进行选择是一个复杂的问题。在上述情况下，您将看到自下而上的版本对于给定的输入运行速度更快。附加函数调用会有一些递归开销，并且在某些情况下，您可能会受到递归深度限制。但这有时只能由自上而下的技术完全抵消，仅计算您所需的内容。自下而上将计算所有较小的输入（对于“较小”的定义），以便找到您的价值。自上而下将仅计算解决问题所必需的值。

1开个玩笑！我只有在使用动态编程后才找到该值。

0
投票

从示例中，我假设没有任何组可以为空。还要假设n，k <= 1000。

dp状态将为remaining Objects和remaining Groups。 f(remObject,remGroup)是将remObject放入remGroup的方式，其中没有任何组比以前形成的组具有更少的对象。

我们将考虑2个案例。

如果要在最左边的组中放置一个对象，我们也需要在所有其他组中放置一个对象。因此，我们必须确保remaining Objects >= remaining Groups。在这种情况下，我们将f(remObject - remGroup, remGroup)添加到答案中。

如果我们不想再将任何对象放在最左边的组中，我们将在答案中添加f(remObject,remGroup - 1)。

基本情况是没有要考虑的组并且放置了所有对象时。

由于任何组都不能为空，因此在调用我们的dp之前，我们将在所有k个组中放入1个对象。

查看代码以获取更多详细信息。

#define mxn 1003
#define i64 long long int
#define mod 1000000007

i64 dp[mxn][mxn];

i64 f(int remObject,int remGroup) {
        if(!remGroup) {
                if(!remObject)
                        return 1;
                return 0;
        }

        if(dp[remObject][remGroup] != -1)
                return dp[remObject][remGroup];

        i64 ans = 0;
        if(remObject >= remGroup)
                ans += f(remObject - remGroup, remGroup);
        ans += f(remObject,remGroup - 1);
        ans %= mod;

         return dp[remObject][remGroup] = ans;
}

int main()
{
        int t,n,k;
        memset(dp,-1,sizeof dp);
        cin >> t;
        while(t--) {
                cin >> n >> k;
                if(n < k)
                        cout << 0 << endl;
                else
                        cout << f(n-k,k) << endl;
        }
        return 0;
}
0
投票

这些被称为partitions with restricted number of parts。这是一个简单的备注（似乎比Scott Sauyet's快10倍）：

function f(n, k, memo={}){
  if (k == 0 && n == 0)
    return 1

  if (n <= 0 || k <= 0)
    return 0

  if (memo.hasOwnProperty([n, k]))
    return memo[[n, k]]

  return memo[[n, k]] = f(n - k, k, memo) + f(n - 1, k - 1, memo)
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')

自下而上（比Scott Sauyet's快50到100倍：]

function f(n, k){
  let dp = new Array(n + 1)
  for (let i=0; i<n+1; i++)
    dp[i] = new Array(k + 1).fill(0)
  dp[0][0] = 1
  
  for (let i=1; i<=n; i++)
    for (let j=1; j<=Math.min(i, k); j++)
      dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1]

  return dp[n][k]
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.