Contraintes données sur les sous-réseaux à somme maximale sur les indices

Question

Comment trouver la somme maximale d'un tableau d'entiers positifs uniques étant donné que certains indices de tableau ne peuvent pas être appariés?

Par exemple, nous avons ce tableau: [8, 2, 1, 3, 9, 4]

éléments à indices (0, 4) et (4, 5) n'aiment pas.

Dans ce cas, la somme maximum serait: 8 + 2 + 1 + 3 + 4 = 18

En supposant qu'il était à l'échelle de 100 entrées et jusqu'à la moitié autant de contraintes, comment aborderez-vous ce problème?

Y a-t-il une structure de données comme un graphique qui serait utile ou du DP? Ma principale préoccupation est avec l'exécution efficace.

Answer 1

Ce que vous essayez de résoudre est le problème maximum-weight independent set. C'est un problème dans la théorie des graphes.

Les indices de tableau correspondent aux sommets d'un graphique. Le poids de chaque sommet est la valeur du tableau à l'index respectif. Dans votre exemple, le sommet 0 a le poids 8 et le sommet 4 le poids 9.

Les paires d'indices de tableau qui ne s'aiment pas correspondent aux bords du graphique. Par exemple, il existe une limite entre les sommets 0 et 4.

Vous recherchez un ensemble d'indices de tableau dans lesquels aucun des deux indices ne se détestent. En termes de graphique, vous voulez un ensemble de sommets dans lesquels aucuns deux sommets ne sont connectés par un bord. Un tel ensemble de sommets est appelé un ensemble indépendant.

Parmi tous les ensembles indépendants, vous voulez celui avec la plus grande somme de poids de vertex. C'est le problème de l'ensemble indépendant de poids maximum.

L'approche par force brute de ce problème essaie tous les sous-ensembles de n sommets pour déterminer le poids maximum. Malheureusement, ce problème est NP-hard. On pense que les problèmes NP-difficiles ne peuvent pas être résolus en temps polynomial. En d'autres termes, vous ne pouvez pas faire beaucoup mieux que l'approche de la force brute.