Aide La Grande Fuite, épreuve régionale 2019, limite de mémoire dépassée

Le test n°3 indique un dépassement de mémoire (115,7 Mio)

Mon idée est prétraiter les données de l'énoncer pour séparer les animaux en groupes d'amis (par un parcours de graphe) auquel j'associe le poids (somme des poids des amis constituant le groupe) et le nombre d'animaux.

J'ai donc deux listes de longeur k (nombre de groupes d'amis): poids et nombre_danimaux, où le groupe d'amis i comprend nombre_danimaux[i] animaux et pèse poids[i]

Il s'agit donc de déterminer un sous ensemble de [|0, k|] qui maximise la somme des nombre_danimaux en respectant la contrainte de poids. J'ai donc simplement listé l'ensemble des parties de [|0, k|] (en éliminant systématiquement ceux dont le poids dépasse la capacité) et j'en prends le maximum.

Cependant la taille de cette liste étant 2^k, je dépasse rapidement la limite de mémoire. Y'a-t-il un autre moyen de trouver ce sous-ensemble sans avoir à tous les lister explicitement? Malheureusement je ne peux pas les détruire au fur et à mesure que je change la valeur de mon maximum, car je construits les sous ensembles à partir des autres sous ensemble déjà formés.

comment faire pour utiliser moins de mémoire?

Salut. T'as bien commencé en groupant les amis ensemble.

Pour ce qui est de la solution, un fois que t'as réduit à des groupes (v,p) avec v le nombre d'animaux et p le poids, tu te retrouves très proche d'une problème très étudié. https://prologin.org/forum/entrainement-3/ressources-concernant-lalgorithmique-900/ Parmi les ressources, l'une d'elle concerne la résolution du problème, et dans les articles connexes tu trouveras le problème similaire à celui ci.

C'est vague mais se faire servir la solution n'apportera rien, j'espère que tu aura l'occasion de découvrir quelques algos intéressants au passage.

Merci beaucoup, j'ai fini par trouver une solution qui passe tous les tests de performance :)