Solveur de problème de sac à dos en ligne

Résolution du problème du sac à dos 0/1

Ce solveur traite le problème classique du sac à dos 0/1 : chaque objet ne peut être choisi qu'une seule fois. Il utilise la programmation dynamique pour trouver une sélection optimale.

Exemple concret

Supposons les objets suivants :

• A : poids 2, valeur 6
• B : poids 3, valeur 10
• C : poids 4, valeur 12

Avec une capacité de 5, la valeur maximale est 16, obtenue en sélectionnant A et B.

Paramètres et traitement

Le solveur accepte de 1 à 200 objets. Les poids doivent être des entiers positifs ne dépassant pas la capacité. Les valeurs peuvent être nulles ou positives jusqu'à 1 000 000 000. La capacité doit être un entier entre 1 et 5000.

Limites

Cet outil ne gère pas les variantes fractionnaires, à multiplicité bornée, multidimensionnelles ou avec contraintes de devise. Les valeurs sont traitées comme des scores abstraits. En cas d'égalité de valeur, une seule sélection optimale est affichée, sans critère secondaire.

Questions fréquentes

Que se passe-t-il si plusieurs combinaisons donnent la même valeur maximale ?

Le solveur affiche une seule sélection optimale. Il ne liste pas toutes les possibilités et ne privilégie pas un critère secondaire comme le poids total le plus faible.

Puis-je saisir des poids décimaux ou des valeurs négatives ?

Non. Les poids doivent être des entiers positifs et les valeurs des entiers de 0 à 1 000 000 000. Les valeurs négatives ne sont pas acceptées.

Le solveur gère-t-il les objets en plusieurs exemplaires ?

Non, c'est un solveur 0/1 : chaque objet ne peut être sélectionné qu'une seule fois. Pour des objets multiples, il faut les saisir comme des entrées distinctes avec des noms uniques.

Vérification rapide

• Le nom de chaque objet est unique et non vide.
• Le poids est un entier positif inférieur ou égal à la capacité.
• La valeur est un entier entre 0 et 1 000 000 000.
• La capacité est un entier entre 1 et 5000.
• Le nombre d'objets est compris entre 1 et 200.