Sac à dos 0/1 (DP)

Choisir des objets pour maximiser la valeur totale sans dépasser la capacité. Chaque ligne représente un objet distinct utilisable une seule fois. Séparer poids,valeur par une virgule, un point-virgule ou un espace. Les lignes vides et celles commençant par # sont ignorées.

Poids et capacité utilisent la même unité libre. Cet outil pédagogique accepte capacité et poids de 0 à 40, jusqu’à 12 objets et des valeurs entières non négatives jusqu’à 1000000. Les poids nuls sont permis ; les objets identiques sont des exemplaires distincts.

La table DP donne la meilleure valeur avec les i premiers objets à la capacité c. Chaque cellule compare ignorer l’objet et le prendre avec la ligne précédente à c−poids. Le chemin surligné retrace la sélection ; en cas d’égalité, la sélection précédente reste choisie. Ni le poids minimal ni toutes les solutions optimales ne sont garantis.

Le calcul est immédiat et utilise O(n × (capacité + 1)) en temps et en mémoire pour n objets. Modifier efface les anciens résultats ; Réinitialiser restaure l’exemple. Les saisies brutes et commentaires sont conservés localement dans ce navigateur, même avec une capacité incomplète. Recalculer après rechargement. Les anciens exemples enregistrés ou partagés restent compatibles. Un brouillon trop volumineux déclenche un avertissement : copier le texte avant de quitter. La version enregistrée précédente est conservée.