Posté par
Ksilver Ksilver
un probleme tes delicat, je par dans l'idee qu'on peut manger des fraction de poires et parcourie des fraction de kilomètre, on admetra (on supposera comme vous voulez) le fais assez evident que toute solution possible et inteligente (cad, sans gachi volontaire style raporter des poire en arrière ou partir sans prendre 1000 poire ou autre) peut s'exprimer de la facon suivante en inversant l'ordre des actions a faire et en decompossant certain trajet en plusieur parti :
on avances les 3000 poires restante de N (N<500) Kilometre en faisant plusieur aleretour, puis de la meme facon on avance les P poires restante de N2 kilometre etc... jusqua arriver a 1000 km...
bon a partir de la on calcule la consomation minimal de poires pour avancer notre tas de P poires de N killometre (avec N inferieur a 500 pour que sa soit possible directement)
on de vra parcourir les N killometre : le nombre de voyage a faire *2 (aller retour) - 1 (pas de retour au dernier voyage)
le nombre de voyage a faire corespont au chifre des millier du nombre de poires restantes, sois [P/1000] (on note [x] la parti entière de x)
pour avancer de N killomètre on va donc consomer N*([P/1OOO]*2-1)), avec cette methode si apr exemple on decompose le trajet a faire en 10 voyage de 100 km il restera :
fin du voyage 1 : 3000 - 100*5 = 2500
din du voyage 2: 2500 - 100*5 = 2000
fin du voyage 3 : 2000 - 100*3 = 1700
fin doyage 4 : 1700-300=1400
fin du voayge 5: 1400-300=1100
fin du voyage 6: 1100-300 = 800
a paritr de la il reste 400 Km a parcourire et 800 poire on arrive a 400 poire a la fin. c bien mais sa n'est pas optimum... pourquoi? car on a gaspiller au moment ou l'on na aps fais d'aret en passant la "barriere" des 1000 on a continuer comme si l'on avait plus de 1000 en consomer donc 3 poire/kilometre alors qu'on pourrait passer a 1 poire/killomètre.
en effet pour optimiser il faur [N/1000] sois le plus petit possible a chaque fois (le killometrage etant constant c la seul variable ! ), etant donner qu'il diminu avec le nombre de poires, mais de facon non linarie il faut le reduire au maximum en consommant le moins de poir possible (le but c quand meme d'avoir des poires a al fin non ?) on peut donc jouer sur le rapport [N/1000]/N qui est evidement a son maximum quand N est multiple de 1000.
il faut donc qua la fin de chacun des voyages on est un nombre de poires multiple de 1000 (on pourra s'amuser a faire des arret intermediraire qui ne modifie pas les nb de bana consomer mais cela na pas d'interet)
bref
1er voyage on consome 5 poires/km on pourra donc parcourire 200 km avant de passer en dessous des 2000 poires, on parcour c'est 200 km on se retrouve avec 2000 banane a 200 km
a partir de la on ne consome plus que 3 poir du kilometre (2*2-1) on peut donc parcourire 1000/3 km avant de passer les mille on se retrouvera a 1000/3+200 km avec 1000 banane et il ne restera plus qua parcourire les kilometre restant en ligne droite en consomant 1 poire/km a la fin il nous restera 1000/3+200 poires soit environ 533,33 poires
la sollution optimal semble donc etre 533+1/3 de poires...
on peut l'optenir de la facon suivante :
on par de 0 avec 1000 poire pour aller jusque a 200 la on depose 600 poir a 200 km et on revien a 0 en consomant les 200 banae restante, arriver a 0 on reitère le processus pour redeposer 600 poir a 200km on se retrouve avec 1200 poire a 200km et 1000 poir et 1 ane a 0km, on enmene les 1000 poires restant a 200 km a l'arriver il en reste 800 ce qui nous fais 2000 au total, on a 2000 poire et 1 ane a 200km...
on en meme 1000 des 2000 poire a 333+1/3 km de plus on en depose 333+1/3 et on en reconsome 333+1/3 pour le retour on enmene les 1000 autres a 333+1/3 il en reste 666+2/3 plus les 333+1/3 deja sur place on arrive a 1000 poires a 533+1/3 km on a plus qua parcourire les km restant et on arrive avec 533+1/3 de poir a l'arriver comme predit ! CQFD