Pour une rencontre familiale, Léa prépare plusieurs éléments qu'elle aimerait apporter. Une seule enveloppe de capacité leur est donnée sur sa feuille. Elle peut laisser des éléments de côté ; elle ne doit donc pas chercher à répartir tous les objets entre plusieurs contenants. Le choix porte sur ceux qu'elle conserve, avec des scores expressément attribués pour l'exercice. Une liste facile à obtenir peut être admissible sans être celle qui rassemble le plus grand score.
Tout le dispositif est créé : objets abstraits, unités de charge, capacité et scores. Chaque objet peut être choisi une fois, entier, ou ne pas être choisi. Les scores ne décrivent ni les goûts des proches ni une valeur marchande. Nous ne testons aucun sac, poids supportable, volume disponible ou trajet. La capacité est seulement une limite d'addition dans le modèle. Les fractions examinées plus loin serviront à comparer des résultats, sans autoriser une remise réelle de morceaux d'objets.
Herschel présente des sacs à dos.
Osprey présente des sacs à dos.
Deuter présente le sac Aircontact Core.
Ces pages ont été lues pour identifier des sacs seulement. Aucun conseil de chargement, capacité ni score n'en est repris.
Une préférence par unité de charge peut laisser le meilleur choix entier de côté
La feuille contient trois objets : A demande dix unités de charge et apporte soixante points, B demande vingt et apporte cent, C demande trente et apporte cent vingt. La capacité est cinquante. Les rapports score sur charge sont donc six pour A, cinq pour B et quatre pour C. Léa commence par suivre cet ordre : elle choisit A puis B. Leur charge totale est trente et leur score cent soixante. C ne tient plus dans les vingt unités restantes.
Une proposition voulait garder la place encore libre comme preuve que la sélection n'était pas terminée. Léa vérifie pourtant qu'aucun objet restant n'y entre entier. Elle ne remet pas un second A, qui n'existe pas dans la liste, et ne réduit pas C de trente à vingt. La sélection A, B est bien une réponse admissible. Ce contrôle ne dit pas encore qu'elle possède le meilleur score. Il ferme seulement la possibilité d'améliorer cette même sélection par l'ajout direct d'un objet restant, sans retirer aucun de ceux qu'elle conserve.
Léa examine ensuite B, C. Cette paire demande exactement cinquante et apporte deux cent vingt. Elle laisse A de côté, bien que son rapport individuel ait été le plus grand. Le changement retire dix unités de charge et soixante points, puis ajoute trente unités et cent vingt points. Il gagne donc soixante points tout en remplissant l'enveloppe. La remise choisie devient B, C. Le refus de C dans les vingt unités restantes de la première proposition ne prouvait pas son exclusion dans toute autre sélection : cette place restante dépendait déjà du choix de A.
Autoriser les fractions fournit une autre comparaison
Pour calculer une borne, Léa ouvre maintenant un exercice auxiliaire où une fraction d'objet porte la même fraction de sa charge et de son score. Ce changement ne devient pas une permission de la remise entière. Dans cet exercice, elle prend A et B, puis deux tiers de C. Les vingt unités encore libres peuvent alors recevoir cette fraction de C et ses quatre-vingts points. La charge atteint cinquante et le score deux cent quarante. Ce résultat appartient au problème auxiliaire, dont les possibilités comprennent les choix entiers mais ne s'y limitent plus.
Léa justifie l'ordre des fractions par un échange de charge. Si une sélection auxiliaire utilise un peu de C tout en laissant une même quantité disponible de A, transférer cette quantité de C vers A conserve la charge totale. Chaque unité transférée remplace quatre points par six et augmente le score de deux. Le même transfert de C vers B gagne un point par unité ; de B vers A, il en gagne également un. Tant qu'un objet de meilleur rapport reste partiellement disponible, remplir d'abord un rapport inférieur ne peut donc être le meilleur choix fractionnaire.
Elle ne peut pas répéter cet échange indéfiniment sur A : cet objet ne fournit que dix unités au total. Après avoir pris toutes ces dix, la meilleure charge restante commence par les vingt disponibles de B. C reçoit ensuite la place qui reste, soit vingt sur ses trente. Ces limites par objet sont conservées dans la preuve. Une autre proposition faisait remplir les cinquante unités par le rapport six de A et annonçait trois cents points. Léa la retire : elle aurait utilisé cinq fois la charge de A sous couvert d'une permission de fractionner un seul exemplaire.
La borne deux cent quarante peut aussi être vérifiée sans décrire les échanges successifs. Léa note a, b et c les charges prises dans A, B et C. Leur score est six a plus cinq b plus quatre c, soit quatre fois leur charge totale, plus deux a, plus b. La charge totale vaut au plus cinquante, a au plus dix et b au plus vingt. Le score ne peut donc dépasser deux cents, plus vingt, plus vingt. La prise de A, B et deux tiers de C atteint ces trois limites ensemble ; elle confirme la borne par une réalisation auxiliaire précise.
Une borne supérieure et une sélection réalisable ne racontent pas le même résultat
Toute sélection entière est autorisée dans l'exercice auxiliaire : choisir un objet revient à prendre sa fraction un, le laisser revient à prendre zéro. Son score ne peut donc dépasser deux cent quarante. B, C est de son côté une sélection entière réalisable à deux cent vingt. Léa conserve les deux nombres avec leurs rôles : elle dispose d'au moins deux cent vingt, tandis que le meilleur choix entier ne peut dépasser deux cent quarante. Elle ne remet pas une sélection intitulée deux cent quarante sans pouvoir en donner les objets entiers.
À cette frontière du raisonnement, la différence de vingt ne certifie pas que le choix B, C est exactement optimal. Elle borne seulement ce qui pourrait encore lui manquer. Une sélection entière meilleure, si elle existait, gagnerait au plus vingt points sur celle déjà trouvée. Léa peut transmettre ce renseignement limité pendant sa préparation, sans inventer la sélection qui gagnerait ces vingt. Lorsqu'elle demande une preuve du meilleur score exact, elle conserve les invitations à examiner dans les branches suivantes au lieu de présenter cette limite d'écart comme leur résolution.
Arrondir la fraction de C ne ferme pas ce travail. La remplacer par C entier donnerait A, B, C, soixante unités, au-delà de la capacité cinquante. La retirer donnerait A, B et cent soixante points, déjà moins que B, C. Léa refuse donc les deux arrondis comme réponses au meilleur choix entier. Ils produisent respectivement une proposition interdite et une proposition admissible moins bonne. La solution auxiliaire avait servi à calculer une borne ; sa proximité avec une fraction un ou zéro n'a pas sélectionné à elle seule les objets qu'il fallait changer ensemble.
Séparer la présence et l'absence d'un objet couvre toutes les réponses
Léa divise les sélections entières en deux familles : celles qui contiennent A et celles qui ne le contiennent pas. Chaque réponse appartient à une de ces familles, une seule. Avec A, la place restante est quarante. Sans A, elle reste cinquante. Le score soixante de A figure seulement dans la première famille. Cette séparation ne choisit pas encore laquelle est la meilleure ; elle donne deux questions plus petites dont les résultats pourront être comparés, sans laisser une sélection de côté entre les deux.
Dans la famille qui contient A, Léa sépare à nouveau la présence et l'absence de B. Avec A et B, la charge est trente, et C ne peut rejoindre les vingt unités libres. Cette branche se termine avec cent soixante points. Avec A mais sans B, C peut entrer : la charge totale est quarante et le score cent quatre-vingts. Prendre C est préférable à ne garder que A, puisque ses cent vingt points sont positifs. Léa conserve donc cent quatre-vingts comme meilleur score de toute la famille qui impose A, avec la paire A, C pour le réaliser.
Dans la famille sans A, B et C peuvent être pris ensemble. Leur charge cinquante respecte la capacité et leurs deux scores sont positifs. Retirer B ou C diminuerait le total ; aucun autre objet ne reste dans cette famille pour le remplacer. Le meilleur score y est donc deux cent vingt. La comparaison des deux familles donne deux cent vingt contre cent quatre-vingts. Léa peut désormais qualifier B, C de meilleur choix entier exact. Cette conclusion vient des branches qui couvrent toutes les réponses, et non du seul échec de l'ordre des rapports.
Une bonne sélection déjà trouvée permet de fermer une branche par sa borne
Dans une préparation indépendante, Léa a déjà conservé B, C à deux cent vingt avant d'examiner en détail les branches avec A. Elle n'a pas besoin de chercher tous les descendants de chaque branche si une borne suffisante les écarte. Pour A et B présents, C n'entre pas entier dans la place restante. Le meilleur score entier de ce nœud est cent soixante. Léa ferme cette branche parce qu'elle ne peut battre le résultat déjà disponible, en conservant la raison de sa fermeture plutôt qu'une simple marque refusé.
La branche avec A et sans B admet encore C. Même en autorisant ses fractions, elle ne dépasse pas cent quatre-vingts : A et C entiers demandent quarante et épuisent tous les objets qui y sont disponibles. Ce plafond reste inférieur aux deux cent vingt conservés. Léa ferme également cette branche. Elle n'a pas utilisé la grande borne initiale deux cent quarante à cet endroit ; elle a recalculé une borne avec B réellement retiré. Garder B dans le calcul aurait donné au nœud la place et les points d'un objet que sa propre condition excluait.
La famille avec A avant ce second partage garde en revanche une borne fractionnaire de deux cent quarante, comme au départ. Elle pourrait encore dépasser deux cent vingt selon cette seule borne. Léa ne la ferme donc pas tout entière à cette première étape. Le partage selon B a fourni les deux limites plus précises, cent soixante et cent quatre-vingts, qui permettent ensuite de la fermer. Le détail d'une branche ne sert pas seulement à trouver une autre liste : il peut resserrer la preuve lorsque le plafond trop large du parent n'avait pas encore permis de décider.
L'ordre d'examen change ce qui est connu pendant la recherche
Si Léa examine d'abord A et B, son meilleur choix réalisé vaut cent soixante. La branche A sans B a une borne cent quatre-vingts, supérieure à ce résultat ; elle ne peut pas être retirée sur cette comparaison. Léa la suit et conserve A, C à cent quatre-vingts. La famille sans A doit encore être examinée et fournit ensuite B, C à deux cent vingt. Les fermetures possibles ont donc changé pendant la recherche, à mesure qu'une meilleure sélection effectivement admissible devenait disponible.
Léa conserve chaque limite de branche avec le meilleur choix connu au moment de sa comparaison. Elle ne raconte pas qu'elle avait déjà écarté A, C grâce aux deux cent vingt lorsque ce résultat n'avait pas encore été obtenu dans cette suite d'examen. Le meilleur score final est le même ; le parcours de justification est différent. Son relevé distingue la découverte d'une sélection et le plafond d'une famille. Cette distinction lui permet de retrouver pourquoi une famille restait encore ouverte sous cent soixante, puis pouvait être fermée une fois deux cent vingt réellement conservés.
Une égalité demanderait enfin de préciser ce que Léa veut produire. Si le plafond d'une branche égalait exactement le score déjà conservé, cette branche ne pourrait pas améliorer la valeur maximale. Elle pourrait néanmoins contenir une autre sélection de même valeur. Pour remettre un seul meilleur choix, Léa peut la laisser de côté sur ce motif ; pour dresser toutes les sélections maximales, elle ne peut pas la supprimer en prétendant qu'aucune nouvelle réponse ne s'y trouve. La condition de fermeture conserve donc l'objet de la recherche, une valeur avec une remise ou un catalogue complet de remises égales.
Une branche séparée conserve A, B et C, sans D, puis ajoute E, de charge cinquante et de score deux cent vingt. Léa prépare cette fois le catalogue de tous les meilleurs choix, pas seulement une liste à remettre. L'ajout reste un objet entier supplémentaire ; il ne remplace pas B et C par une copie portant une autre lettre.
Elle a déjà trouvé B, C à deux cent vingt lorsqu'elle arrive à la branche où E est présent. E occupe seul toute la capacité et atteint également deux cent vingt ; aucun autre objet ne peut l'accompagner. Fermer cette branche parce qu'elle ne dépasse pas le résultat conservé laisserait le meilleur score exact, mais retirerait E du catalogue demandé. Léa inscrit donc E comme seconde réponse, puis garde la branche sans E pour B, C. Les deux listes ont la même charge et le même score, avec des objets différents. Toutes les sélections contenant E se réduisent ici à E seul ; sans E, les anciennes branches avaient déjà donné B, C comme seul maximum. Ces deux contrôles ferment le catalogue avec exactement deux réponses, sans confondre l'égalité du score avec l'identité de la remise.
L'hôte demande ensuite de choisir, parmi ces seules réponses maximales, celle qui contient le moins d'objets. Léa retient E, une pièce, et laisse B, C, deux pièces, dans le catalogue comparatif. Elle refuse de substituer A, une pièce également mais seulement soixante points : le départage intervient après le score maximal, il ne remplace pas cette première exigence. Pour cette remise unique, fermer la branche E à l'égalité aurait donc perdu la réponse souhaitée sous le nouveau départage. Léa conserve le score et le nombre dans l'ordre de la demande, puis inscrit E sur la liste active. Le catalogue n'est pas réécrit pour supprimer B, C, qui reste une autre sélection maximale dans la recherche précédente.
Une sélection partielle peut dominer une autre sous le même reste
Léa prépare ensuite un autre relevé où les trois premiers objets A, B et C ont déjà été examinés, mais où un nouvel objet D de charge dix et de score soixante-dix sera encore disponible. Elle compare deux états partiels : C seul demande trente et vaut cent vingt ; A, B demande également trente et vaut cent soixante. Les deux états possèdent le même objet encore à examiner, D. Toute continuation possible après C peut donc être ajoutée après A, B, avec une même charge finale et quarante points de plus.
Elle peut retirer l'état C de cette recherche du meilleur score, sans retirer l'objet C de toutes les listes. Si D est ajouté à chacun, C, D vaudrait cent quatre-vingt-dix pour quarante unités, alors que A, B, D vaut deux cent trente pour cette même charge. Si D est laissé, l'écart de quarante reste également présent. La suppression porte sur un état à une frontière déterminée, pas sur la valeur générale d'un objet. Léa conserve C dans l'état A, C, qui présente une autre charge et un autre score à cette même frontière.
Ce second état A, C demande quarante et vaut cent quatre-vingts. Il n'est pas dominé par A, B, dont la charge est trente mais le score seulement cent soixante. Le premier possède davantage de points ; le second davantage de place libre. Avec D, A, C, D atteint cinquante et deux cent cinquante points. A, B, D atteint quarante et deux cent trente. Léa retient A, C, D dans cette nouvelle feuille. Garder uniquement l'état partiel le moins chargé aurait supprimé celui qui fournit la meilleure continuation après réception de D.
L'ancienne meilleure paire B, C demandait cinquante et valait deux cent vingt. Elle ne peut recevoir D. Léa ne conserve pas seulement ce plus grand score partiel en effaçant A, C à cent quatre-vingts : leurs places restantes diffèrent. L'ajout de D rend ici cette place décisive. Elle garde donc les états qui ne sont pas dépassés à la fois en score et en charge. Cette règle ne promet pas que le plus petit objet ou le meilleur rapport aura toujours gagné ; elle conserve précisément les compromis que ces deux classements isolés auraient effacés.
Comparer des objets n'autorise pas la même suppression que comparer des états
Léa vérifie la différence sur une petite feuille séparée : X demande deux unités et apporte cinq points ; Y demande trois et apporte quatre ; la capacité est cinq. X est plus léger et vaut plus que Y. Une proposition en déduisait qu'il fallait retirer Y avant toute recherche. Léa la refuse : elle peut choisir X et Y ensemble, avec cinq unités et neuf points. Retirer Y laisserait seulement cinq points avec X. Les deux objets n'étaient pas deux versions exclusives d'une même pièce ; leurs choix pouvaient s'additionner.
Le remplacement supposé aurait demandé un second X pour prendre la place de Y tout en conservant le premier. Ce second exemplaire n'est pas disponible. Dans la comparaison des états C et A, B, au contraire, les trois premiers objets étaient déjà tous passés dans l'examen ; la même liste restante D pouvait compléter chacun. Léa conserve cette condition de frontière commune dans sa suppression. Une ressemblance entre poids et valeurs ne suffit donc pas à déplacer la justification d'un état complet du passé vers un objet qu'on pouvait encore choisir avec un autre.
La liste des objets disponibles devient ainsi une donnée de l'état, même lorsqu'elle n'est pas imprimée dans une colonne de nombres. Comparer deux charges et deux scores ne suffit pas si les continuations autorisées diffèrent. Léa peut réduire sa feuille après avoir marqué le même préfixe examiné pour les états comparés. Elle ne transfère pas cette réduction à une feuille où l'un pourrait encore choisir C et l'autre l'aurait déjà consommé. Le contrôle conserve ce que la suppression garantissait réellement : une continuation remplaçable, avec une charge au plus égale et un score au moins égal.
Modifier la capacité ne donne pas le même gain dans les deux exercices
Une dernière comparaison reprend seulement A, B et C, mais limite la capacité à quarante-neuf. La paire B, C n'est plus admissible, puisqu'elle demande cinquante. A, C garde sa charge quarante et ses cent quatre-vingts points ; A, B garde trente et cent soixante. Les objets seuls ne dépassent pas cent vingt. Léa retient donc A, C à cent quatre-vingts pour cette feuille. La place libre de neuf n'autorise pas B, dont les vingt unités sont encore indivisibles. La remise conserve deux objets et laisse cette place inutilisée.
L'exercice fractionnaire prend toujours A et B, puis dix-neuf unités sur les trente de C. Il atteint deux cent trente-six, quatre points seulement sous la borne initiale deux cent quarante. Passer de quarante-neuf à cinquante augmente pourtant le meilleur score entier de cent quatre-vingts à deux cent vingt, soit quarante points. Léa refuse donc d'utiliser la progression de la borne comme mesure du gain entier. Une seule unité supplémentaire a permis la paire B, C complète ; elle n'a pas seulement acheté quatre points d'une portion plus grande de C dans la remise choisie.
La préparation garde ainsi les objets de sa meilleure sélection et les limites qui l'ont prouvée. Deux cent quarante était une borne auxiliaire, deux cent vingt une remise entière avant l'ajout de D, et deux cent cinquante la réponse à la liste enrichie. Léa ne les réunit pas sous une promesse identique. Elle peut fermer des branches ou des états à partir de preuves précises, sans retirer arbitrairement les objets qui ont fourni la meilleure continuation dans une autre feuille.