Problème du sac à dos

[Zamentur]

Le problème du sac à dos est un problème connu en recherche combinatoire dans le domaine de la programmation dynamique.

Le principe c'est qu'on a des objets chacun avec un poids et une( ou plusieurs) valeur.
Le sac à dos à une contenance maximum et il s'agit alors de maximiser la valeur total mise dans le sac à dos.

Je me dis que c'est un trucs que l'on peux inclure afin d'aider le joueur, voici par exemple une situation:
Le joueur va à son coffre ou ils laissent tout les objets qu'il n'emporte pas sur lui. Là il a un sac pouvant contenir 14kg rempli avec 6kg d'objet, il souhaite partir au combat et privilégier les objets d'attaque. Là le programme lui propose une liste d'objets qu'il peut modifier si il le souhaite.

Un petit lien expliquant comment résoudre le problème:
http://fr.wikipedia.org/wiki/Probl%C3%A8..._dynamique

Bien sur dans nos cas les valeurs sont plutôt des combinaison de valeur, il faut donc s'adapter...

Bref je me disais que çà pourrait avoir son intérêt de proposer des solutions par défaut au remplissage d'un sac...

[wild-D]

ça marche aussi pour plein d'autre type de jeu, genre les jeux de stratégie spatiale, dans lesquels tu dois concevoir les designs de tes vaisseaux. Ca permet de préremplir/ou compléter les composants (armement, propulsion, blindage, etc...) du vaisseaux en fonction du "type de vaisseau".

c'est sympa mais on se trouve généralement vite limité par les critères que l'on peu donner. Ce qui oblige à repasser derrière, et dans ces cas là bien souvent on y gagne rien. (va donc expliquer à ce genre "d'automatisme" que tu veux pas utiliser le meilleure propulsion mais une plus ancienne qui consomme peut-être 10% de plus mais à un temps de construction inférieur, qui vu tes stations spatiale de production va te permettre de produire 15% de vaisseaux en plus dans le même temps... ) Bien des critères d'optimisation ne sont pas des maximisation pures et dures; et font souvent appel à des critère "complexe/stratégique/contextuel".

perso je trouve finalement que ce genre de fonctionnalité (pour ce que j'ai rencontré) et une aide au démarrage très sympa (quand tu connais pas bien le jeu difficile de savoir comment remplir ton sac; comment concevoir tes vaisseaux,...) obtenir donc une proposition sur 1 ou 2 critère simple, c'est très utile.
Mais je trouve pas que ce soit une réelle aide/gain de temps (pour s'éviter des tâche qui pourrait être répétitive) pour les joueurs avancés (manque de flexibilité des critères).
(mais bon ce jugement ça vient surement aussi de mon coté optimisateur-perfectionniste^^)