[2020 - LV4] Exploitation Equitable - test de performance échoué

J'en ai marre et faut que je vide mon sac.

Bonjour à tous ,

Pour cette exercice consistant à repartir en 2 groupe de valeur d'une liste de n élément les plus proches.

Je m'y suis pris comme bon nombre de gens je pense i.e je prends la moitié de la somme que j'apelle Cet je fais un probleme du sac a dos cherchant a remplir un max ce sac a dos de capacité C. Pour ce faire je fais une bonne grosse matrice de dim C+1*n+1 que je remplis recursivement histoire de calculer le moins de case possible

Problème en arrivant au test de performance j'explose rapidement la mémoire dispo ,

Je voulais donc savoir si des gens connaissaient une méthode pour résoudre le problème du sac à dos sans se trainer une énorme matrice (j'ai essayé avec un dictionnaire et c'est pas spécialement mieux)

Et je voulais aussi savoir si des gens avait trouvé une autre méthode plus accessible et moins couteuse pour attaquer ce problème

Bonjour,

Il y a effectivement une optimisation pour passer sous la barre du c+1 * n+1 et optimiser de beaucoup ta complexité, prenons par exemple un cas à l'itération n, as-tu besoin de celle n-1, n-2..., la réponse est que l'on a uniquement besoin de celle n-1, on peut donc garder deux listes qu'on inverse à chaque itération pour que la liste a soit toujours celle de l'itération précédente et la b soit toujours effacée et remplacée. On peut donc atteindre une complexité en mémoire de c+1 * 2. Et cette astuce est valable pour un certain nombre d'algorithmes dynamiques. Ensuite, pour ma part, les tests de performances sont passés avec l'algorithme de base du sac à dos en Java.

Merci beaucoup pour ta réponse et en effet, de maniere itérative ça sert a rien de garder toute ses colonnes au fur et a mesure. je devrais donc passer tranquillement les test de perf

thimote75

Bonjour,

on peut donc garder deux listes qu'on inverse à chaque itération pour que la liste a soit toujours celle de l'itération précédente et la b soit toujours effacée et remplacée.

Toute fois j'avais commencé a faire ça de maniere récursive histoire de pas compléter de case ""inutile"" et ne faire que les capacité réellement obtenable pour un temps d'exécution optimale. or si je fais de cette maniere je ne peux pas utiliser ton optimisation , existe il donc une sorte de combinaison des deux méthode alliant O(C) niveau mémoire et calcul judicieux ?