Bonjour, Bravo pour cette vidéo très claire sur le sujet. Pouvez-vous vous détailler plus avant la méthode de réduction à un problème polynomial si k est fixé ? Merci
Bonjour. J'ai repris un résultat annoncé dans le livre "Computers and intractability" de Garey et Johnson à la page 226 qui est une référence (j'ai conscience que c'est un argument d'autorité). Notez que ça resterait NP-complet avec k fixé mais résoluble en temps pseudo-polynomial (c'est à dire polynomial par rapport à la valeur des entiers donnés en entrée et non par rapport à leur taille). Cela semble (je dis ça avec précaution) aussi ce que dit l'article "Bin packing with fixed number of bins revisited" de Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter. La question a été posée explicitement sur stack-exchange il y a 4 ans sans réponse... math.stackexchange.com/questions/3280547/pseudo-polynomial-algorithm-for-bin-packing-with-fixed-number-of-bins Tout ça pour dire que ça ne paraît pas si simple. Je n'y ai pas plus réfléchi, désolé. Et ce n'est pas le truc que je fais en 2 minutes. En tout cas merci pour la question qui montre qu'il faut prendre les résultats avec prudence (mais on ne peut pas tout vérifier à fond non plus) ; même si c'est probablement juste.
