Nombre de façons de diviser n objets en k groupes, de telle sorte qu'aucun groupe n'aura moins d'objets que les groupes formés précédemment?

Question

Exemple : n=8, k=4 Réponse : 5

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

J'ai pensé appliquer la programmation dynamique pour compter le nombre de façons de diviser 8 objets en 4 groupes, mais je ne comprends pas comment garder une trace du nombre d'objets dans le groupe précédent.

Approche DP :

for(int j=0;j<=n;j++)
{
    for(int i=1;i<=k;i++)
    {
        if(j

`

Veuillez m'aider avec l'approche. Je suis relativement nouveau en DP.

`

Answer 1

Il s'agit des partitions avec nombre restreint de parties. L'idée derrière la récurrence, qui est égale au nombre de partitions dont la plus grande partie est k (la preuve est laissée en lecture courte et intéressante), est que si la plus petite partie de la partition est 1, nous avons ajouté 1 à toutes les partitions de n - 1 en k - 1 parties (pour garantir que la plus petite partie est 1); et si la plus petite partie n'est pas 1, nous avons ajouté 1 à chacune des k parties dans toutes les partitions de n - k en k parties (garantissant que chaque partie est supérieure à 1).

Voici une mémorisation simple:

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

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

  let key = String([n, k]) // Merci au commentaire de l'utilisateur633183

  if (memo.hasOwnProperty(key))
    return memo[key]

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

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

Voici le bas-haut:

function f(n, k){
  let dp = new Array(n + 1)
  for (let i=0; i

Answer 2

Mise à jour

Bien que toute la discussion ci-dessous soit toujours utile, la réponse de propose un algorithme sous-jacent beaucoup plus agréable qui nous permet de sauter mon paramètremin. (Je savais que je devrais avoir vérifié ça!) Cette compréhension permet une amélioration significative des performances par rapport à l'algorithme utilisé ci-dessous.

---

Pensez à la programmation dynamique (DP) comme une technique d'optimisation simple qui peut accélérer certaines procédures récursives. Si vos appels récursifs se répètent (comme pour les nombres de Fibonacci), alors stocker leurs résultats peut accélérer considérablement votre programme. Mais la logique sous-jacente est toujours un appel récursif. Alors résolvons d'abord ce programme de manière récursive et voyons où nous pourrions appliquer l'optimisation de DP.

(8, 4) avec seulement cinq solutions est assez petit pour que, même si le temps est algorithmiquement exponentiel, il soit encore probablement gérable. Essayons une récursion simple. Et au début, construisons en fait la sortie au lieu de la compter afin de vérifier que nous faisons les choses correctement.

Cette version est basée sur l'idée que nous pouvons définir le premier nombre de la liste, en gardant une trace de cette valeur comme minimum pour les éléments restants, puis recommencer pour les positions restantes. Enfin, essayons à nouveau avec un nombre initial plus élevé. Ainsi que nos entrées n et k, nous devrons également garder un paramètre min, que nous commençons à 1.

Voici une version:

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]]
)

(Vous n'avez pas spécifié un tag de langage; si cette syntaxe Javascript ES6 n'est pas claire, nous pouvons réécrire dans un autre style.)

Étant donné que cela semble correct, nous pouvons écrire une version plus simple juste pour compter les résultats:

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
)

Mais si nous allons essayer un ensemble plus grand, disons f(1000, 10) (qui, par inspection, devrait être 8867456966532531), cela pourrait prendre un peu de temps à calculer. Notre algorithme est probablement exponentiel. Il y a donc deux manières dont nous pourrions aborder la programmation dynamique pour cela. L'approche la plus évidente est l'approche 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')

Déterminer les limites correctes ici est délicat, ne serait-ce que parce que la récursion est basée sur une valeur croissante de min. Il est probable que nous calculons des choses dont nous n'avons pas besoin en cours de route.

C'est aussi du code laid, perdant l'élégance et la lisibilité de l'original tout en ne gagnant que des performances.

Nous pouvons toujours conserver l'élégance en mémorisant notre fonction; ceci est l'approche top-down. En travaillant avec une fonction memoize réutilisable, nous pouvons utiliser notre solution récursive presque intacte:

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 transforme une fonction qui calcule ses résultats à chaque appel en une fonction qui ne calcule ces résultats que la première fois qu'elle voit un ensemble spécifique d'entrées. Cette version vous oblige à fournir une fonction supplémentaire qui transforme les arguments en une clé unique. Il y a d'autres façons d'écrire cela, mais elles sont un peu plus laides. Ici, nous transformons simplement (8, 4, 1) en "8-4-1", puis stockons le résultat sous cette clé. Il n'y a pas d'ambiguïté. La prochaine fois que nous appelons avec (8, 4, 1), le résultat déjà calculé sera renvoyé instantanément à partir du cache.

Remarquez qu'il y a une tentation d'essayer

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

Mais cela ne fonctionne pas, si les appels récursifs dans f pointent vers f. Et s'ils pointent vers g, nous avons déjà mélangé la mise en œuvre et f n'est plus autonome, donc il y a peu de raison pour cela. Ainsi nous l'écrivons comme memomize(createKey, (...args) => {...}). Des techniques avancées qui offrent des alternatives dépassent le cadre de la discussion ici.

---

La décision entre DP bottom-up et DP top-down est une question compliquée. Vous verrez dans le cas ci-dessus que la version bottom-up s'exécute plus rapidement pour l'entrée donnée. Il y a un surcoût récursif pour les appels de fonction supplémentaires, et dans certains cas, vous pourriez être soumis à des limites de profondeur de récursion. Mais ce surcoût est parfois entièrement compensé par la technique top-down ne calculant que ce dont vous avez besoin. Le bottom-up calculera toutes les entrées plus petites (pour une certaine définition de "plus petites") afin de trouver votre valeur. Le top-down ne calculera que les valeurs nécessaires pour résoudre votre problème.

---

1 Une blague! J'ai trouvé la valeur seulement après avoir utilisé la programmation dynamique.

Answer 3

De l'exemple, je suppose que aucun groupe ne peut être vide. Je suppose également que la valeur de n, k <= 1000.

Les états dp seront Objets restants et Groupes restants. f(remObjet, remGroupe) sera le nombre de façons de placer remObjet dans remGroupe où aucun groupe n'aura moins d'objets que les groupes précédemment formés.

Nous examinerons 2 cas.

Si nous voulons placer un objet dans le groupe le plus à gauche, nous devrons également placer un objet dans tous les autres groupes également. Nous devons donc nous assurer que Objets restants >= Groupes restants. Dans ce cas, nous ajouterons f(remObjet - remGroupe, remGroupe) à notre réponse.

Si nous ne voulons plus placer d'objet dans le groupe le plus à gauche, nous ajouterons f(remObjet, remGroupe - 1) à notre réponse.

Et le cas de base sera lorsque aucun groupe n'est plus à considérer et que tous les objets sont placés.

Comme aucun groupe ne peut être vide, avant d'appeler notre dp, nous mettrons 1 objet dans tous les k groupes.

Regardez le code pour plus de détails.

#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;
}

Answer 4

La solution mémorisée peut être encore améliorée en ajoutant quelques vérifications. Si n, k sont égaux, la réponse est 1. Nous n'avons pas besoin de récursion pour 1000,1000. De plus, si k est égal à 1, peu importe la valeur de n, la réponse est 1. 1000,1 est égal à 1, ce qui permet d'économiser de la mémoire et du temps. Code mis à jour : Impossible d'ajouter cela en commentaire à la solution précédente en raison de ma faible réputation, désolé. Vous pouvez également trouver une explication simple ici : N into K groups recursion.

function f(n, k, memo = {}) {
    if (k == 0 && n == 0) return 1;
    if (k == 1 && n != 0) return 1; // lorsque k est égal à 1, peu importe la valeur de n
    if (n == k) return 1; // lorsque k et n sont égaux.

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

    let key = String([n, k]); // Merci au commentaire de l'utilisateur633183

    if (memo.hasOwnProperty(key)) return memo[key];

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