Répartition des ressources w.r.t. capacité individuelle - est-ce un problème de sac à dos?

Question

J'ai un problème comme suit:

1. J'ai quelques emplacements de bureaux et des ressources avec des capacités différentes (nombres entiers).
2. Je veux distribuer toutes les ressources à différents emplacements de bureau pour trouver la meilleure façon de les diviser presque également entre les emplacements afin que les capacités de tous les emplacements de bureau soient équilibrées autant que possible. Quelques éléments à garder à l'esprit:

• La différence entre le nombre de ressources dans chaque bureau ne doit pas être supérieure à un. • La capacité de chaque emplacement de bureau (atteinte en ajoutant des capacités individuelles) devrait être presque aussi égale que possible les uns aux autres.

J'ai fait des recherches sur Internet et j'ai découvert l'algorithme Knapsack et l'algorithme Bin-pack qui semble proche de ce problème. Par exemple Nombre de bureaux: 3; Nombre de personnes = 8; Capacité de personnes = 10, 20, 5, 150, 90, 200, 250, 140 (valeurs de capacités des 8 ressources);

Les numéros ci-dessus sont juste un échantillon. Il peut atteindre 1000+ pour les ressources et la valeur des capacités respectives. Le nombre de bureaux peut également varier.

Je n'ai pas démarré la partie programmation sauf si je suis sûr que le chemin que je vais prendre est correct. Je demande votre aide pour me guider vers une direction correcte pour résoudre ceci. De plus, si vous pouvez partager un pseudo-code probable pour cela, cela vous sera d'une aide précieuse.

Merci!

Answer 1

C'est le problème du sac à dos ou est au moins aussi difficile (considérons une instance où il n'y a que deux bureaux), donc l'obtention de la meilleure solution sera très difficile. Vous pouvez essayer d'utiliser une heuristique d'optimisation générique comme le recuit simulé: http://en.wikipedia.org/wiki/Simulated_annealing