7
votes

Algorithme récursif à retour d'arrière-plan pour résoudre le problème de partitionnement

Hey, je cherche une aide d'aide pour trouver un algorithme qui divise une gamme de nombres positifs en k-parties de sorte que chaque partie ait la même somme ... Disons que nous avons

1,2,3,4,5,6,7,8,9 FR K = 3 THN L'algorithme devrait le partitionner comme ceci 1,2,3,4,5 | 6,7 | 8,9 L'ordre des éléments ne peut pas être changé ... La recherche d'un algorithme gourmand est facile, mais je recherche une version de retour en arrière qui retourne toujours la solution optimale ...

Annyone a eu des indices?

algorithm recursion partitioning backtracking partition-problem

0 commentaires

3 Réponses :

5
votes

Qu'entendez-vous par solution optimale? Je crois que vous voulez dire celui qui minimise la somme de chaque distance de partition à la partition optimale. La partition optimale serait la partition que la somme des éléments est égale à la somme totale divisée le nombre de partitions.

Si cela ne vous dérange pas de l'efficacité, alors peut-être que cette approche rugueuse est suffisamment bonne pour vous. Je n'ai pas testé l'algorithme pour vérifier que c'est exactement l'exactitude, alors soyez prudent. xxx

0 commentaires

5
votes

Voici une solution qui n'utilise aucune structure de données dynamique telle que des listes. Ils sont totalement inutiles et feraient en pratique rendre l'algorithme beaucoup plus lentement que nécessaire.

Laisse K être le nombre de partitions ici et n Soyez le nombre d'éléments de votre tableau. P>

int start[K];

void register() {
   /* calculate the error between minimum and maximum value partitions */
   /* partition boundaries are start[0], start[1], start[2], ... */
   /* if lower error than previously stored, remember the best solution */
}

void rec(int s, int k) {
  if (k == K) register();
  for (int i = s; i < N; i++) {
    start[k] = i;
    rec(i + 1, k + 1);
  }
}

/* entry */
start[0] = 0;
rec(1, 1);
/* then output the best solution found at register() */

0 commentaires

0
votes

Voici un algorithme récursif en JavaScript. Cette fonction renvoie les totaux que chaque travailleur sera attribué. Disons que les livres de tableau d'entrée sont une gamme de nombres positifs que vous souhaitez diviser aussi équitablement que possible en k-pièces (disons parmi les travailleurs K)

Voici un violon de travail: https://jsfiddle.net/missyyssi/jhtk8vnc/3/ < Pré> xxx

0 commentaires