algorithme des k sous-ensembles égaux

Question

Le système de gestion de l'information est un système de gestion de l'information qui permet à l'utilisateur d'accéder à l'information et de la partager avec d'autres personnes ou organisations.

ex. vecteur à 9 éléments

x = {2,4,5,6,8,9,11,13,14}

J'ai besoin de générer tous les sous-ensembles disjoints k=3 avec une somme = 24 l'algorithme doit vérifier s'il existe k sous-ensembles disjoints ayant chacun une somme d'éléments 24, et les lister par ordre croissant (dans le sous-ensemble et entre les sous-ensembles) ou voir si la solution n'existe pas.

Solutions

solution 1 : {2 8 14} {4 9 11} {5 6 13}

solution 2 : {2 9 13} {4 6 14} {5 8 11}

T

Answer 1

Malheureusement, la contrainte Le problème des k-sous-ensembles est un problème difficile ... et si vous voulez générer tous de tels sous-ensembles, vous n'avez pas d'autre choix que de évaluer de nombreux candidats possibles .

Vous pouvez effectuer quelques optimisations pour réduire l'espace de recherche.

Étant donné un domaine x contenant des valeurs entières, Etant donné une cible entière positive M, Étant donné une taille k entière positive pour le sous-ensemble,

1. Lorsque x ne contient que des entiers positifs, et compte tenu d'une borne supérieure M, supprimez tous les éléments de x supérieurs ou égaux à M. Il est impossible qu'ils fassent partie du sous-ensemble.
2. De même, pour k > 1, un M donné et un x contenant des entiers positifs, supprimez tous les éléments de x qui sont plus grands que M + min0 + min1 ... minK. Il s'agit essentiellement de supprimer toutes les grandes valeurs qui ne peuvent pas faire partie du sous-ensemble, car même en sélectionnant de petites valeurs, elles donneront une somme supérieure à M.
3. Vous pouvez également utiliser le principe d'exclusion pair/impair pour réduire votre espace de recherche. Par exemple, si k est impair et M pair, vous savez que la somme contiendra soit trois nombres pairs, soit deux nombres impairs et un pair. Vous pouvez utiliser cette information pour réduire l'espace de recherche en éliminant les valeurs candidates de x qui pourrait faire partie de la somme.
4. Trier le vecteur x - cela permet d'exclure rapidement les valeurs qui ne peuvent pas être incluses dans la somme.

Beaucoup de ces optimisations (autres que l'exclusion pair/impair) ne sont plus utiles/valides lorsque le vecteur x contient des valeurs négatives. Dans ce cas, vous devez pratiquement effectuer une recherche exhaustive.

Comme le souligne Jilles De Wit Si X contient des nombres négatifs, vous pourriez ajouter la valeur absolue de la plus petite valeur de X à chaque membre de X. Cela ramènerait toutes les valeurs dans la plage positive, ce qui rendrait à nouveau possibles certaines des optimisations que j'ai décrites plus haut. Cela suppose toutefois que vous puissiez représenter avec précision les valeurs positives dans la plage élargie. Une façon d'y parvenir serait d'utiliser en interne un type plus large (par exemple long au lieu de int) pour effectuer la recherche de sélection du sous-ensemble. Dans ce cas, n'oubliez pas de réduire les sous-ensembles de résultats de ce même décalage lorsque vous renvoyez vos résultats.