Besoin de trouver une formule

[Ducklefélé]

Bonjour à toutes et à tous,
J’ai besoin de trouver une formule à mon problème. J’ai des cartons avec des tubes rangés en ligne. Le nombre de tubes par rangée est variable. Pour enlever les tubes du carton j’ai plusieurs possibilités de prise : 1=Prise par 6 ; 2=Prise par 5 ; 3=Prise par 4.
Mon problème, trouver la manière la plus efficace de vider le carton en limitant le nombre de prise.
Exemple : 32 tubes sur 1 rangée, l’idéal serait de faire 2 prises de 6 et 4 prises de 5. Pourriez-vous m’aider ?
Merci d’avance.

[lyceen95]

Pour cet exemple avec 32, tu peux aussi faire 4 prises de 6, et 2 prises de 4. Je pense que de ton point de vue, c'est équivalent. Mais la démarche que je propose va arriver à 2 prises de 6 et 4 prises de 5, comme toi.

Tu as 3 tailles possibles : 4,5,6 T1=4, T2=5 et T3=6 Du plus petit au plus grand.
Tu as un nombre Total : NT = 32 dans l'exemple.

Dans cette démarche, on va chercher des solutions avec uniquement des prises de 5 ou 6 pièces.

Tu divises NT par T3 : 32 divisé par 6 donne Q=5, et il reste R=2 (Q=Quotient, R=Reste)
Si la division tombe juste, c'est fini , Tu fais exacteement Q prises de taille T3.
Si la division ne tombe pas juste ( c.a.d si le reste R n'est pas nul), alors il faudra au moins Q+1 prises.

Si tu fais Q+1 prises, tu vas avoir un total de (Q+1)*T3. , Donc un total trop élevé. Trop élevé de combien ?
Tu calcules donc E = (Q+1)*T3 - NT
Et tu vas faire Q+1 prises : E prises avec 5 pièces , et les autres prises avec 6 pièces.
Cette technique marche si on est dans ton cas (Les prises sont de tailles 6 ou 5, et l'écart est de 1). Si l'écart n'est pas de 1, il faut adapter cette formule.

Si le nombre de pièces à prendre est assez élevé, cette méthode marche, et donne le résultat optimal.
Pour des nombres de pièces plus petits, ça ne marchera pas.
Par exemple, pour 19 pièces, ce calcul dirait :
Q=3 et R=1
Il faut Q+1=4 prises.
(Q+1)*6-19, ça donne 5.
Parmi les 4 prises, il faut donc 5 prises de taille 5 et les autres de taille 6 : ça ne colle pas.

Dans cette démarche, on cherche une solution avec uniquement de prises de 5 ou 6 pièces. Quand ça n'aboutit pas (exemple pour 19 pièces), on peut dire :
Je prends une prise de 4 pièces, il faut donc que je fasse différentes prises pour essayer d'arriver à 19-4=15.
Et on applique l'algorithme ci-dessus pour 15.
Et ça marche. L'algorithme ci-dessus nous dit que pour 15, la bonne solution est de faire 3 paquets de 5.

Si avec une prise de 4 pièces, ça n'aboutit toujours pas, on va passer à 2 prises de 4 pièces, puis 3 etc etc.

Si tu cherches une solution générale, il peut y avoir des astuces.
Par exemple, si les prises doivent être de taille 9, 12 ou 14, et si tu dois tirer 101 pièces, 101 est impair, et donc tu es sur qu'il faudra au moins une prise avec 9.