sac à dos probl_m avec coût de transition

Question

Je joue à un jeu où vous pouvez programmer l'IA d'un poireau pour lutter contre d'autres poireaux (leekwars, assez divertissant).

Un poireau a quelques points d'action par tour, disons 10.

Il a une portée de l'arme infligeant des dégâts D pour un coût du point d'action C. Par exemple, un pistolet: 20 points de dégâts pour 3 points d'action, etc.

Il possède une gamme de sorts, similaire aux armes. Par exemple, étincelle: 16 points de dégâts pour 3 points d'action.

Je voudrais infliger le maximum de dégâts pendant mon tour.

Je pensais que c'était un simple problème de havresac quand j'ai découvert que:

Avant d'utiliser une arme, vous devez l'équiper, et que les coûts 1 point d'action. Vous n'avez pas besoin de le rééquiper pour le réutiliser par la suite, mais vous avez besoin de 1 point d'action pour changer d'arme. Tout sort peut être utilisé sans l'équiper.

J'ai essayé, sans succès, de formaliser ceci comme un problème de programmation de type knapsack ou linéaire.

Mon idée principale serait d'introduire par exemple une arme first_pistol traitant 3 dégâts pour 3 + 1 points d'action, et d'introduire la contrainte (C1) que first_pistol peut être utilisé qu'une seule fois et (C2) qui pistol ne peut être utilisé si first_pistol a été utilisé. Mais je ne suis pas sûr de savoir comment formaliser (C2).

Auriez-vous d'autres approches ou commentaires sur mon approche?

Answer 1

Plutôt qu'un problème de sac à dos, cela me semble un problème d'ordonnancement! Vous avez une «machine» qui fonctionne pour 10 unités («temps») (points d'action). Différents «produits» (armes) ont des temps de traitement différents (leurs points d'action). Si vous changez de 'type de produit' (arme), vous obtenez un temps d'installation de 1. Le modèle d'ordonnancement sous-jacent sera en fait assez basique, alors cherchez quelques formulations LP standard :)