C'est le Frobenius Problem qui est en général NP-Hard.
Pour les petites instances, des algorithmes raisonnablement rapides sont cependant connus.
Le papier ici: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf semble décrire les algorithmes précédents (qui inclut une application de l'algorithme de plus court chemin de Dijkstra!) Plus il donne un nouvel algorithme qui est apparemment plus rapide que les précédents. Dans tous les cas, pour le cas où il n'y a que 2 nombres, a et b tels que gcd (a, b) = 1, trouver i, j> = 0 tel que i + b j = M j = M est facile à résoudre.
Il est également connu qu'un nombre quelconque supérieur à (a-1) (b-1) peut être représenté sous la forme d'un i + b j, avec i> = 0 et j> = 0. Le nombre de Frobenius est défini comme le plus grand nombre qui ne peut pas être représenté sous cette forme, et existe quand n> = 2 et gcd (a, b, c ...) = 1.
Donc dans votre cas, si les nombres impliqués sont assez petits, vous pouvez trier le tableau, trouver le 'plus petit' deux a et b tels que gcd (a, b) = 1 et voir si M> (a-1) (b-1), qui peut être résolu juste en utilisant a et b. Si M < = (a-1) (b-1), et a et b sont assez petits, vous pourriez juste être capable de le forcer.
Une bonne question, mais une clarification pour ce que le résultat préféré est. En supposant a, b, c sont les durées, tandis que i, j, k sont la quantité de chaque durée, préférez-vous le moins de nombre de durées (i + j + k est minime) ou moins de durées plus longues (prioriser valeur de a, b, c)? –
http://stackoverflow.com/questions/1467907/ (complexe mais plutôt optimal) – sdcvvc
Je veux juste savoir si une combinaison existe! – user350887