Bonjour,

J'ai concocté un problème pour vous mes amis zér0s

Voici le problème:

Citation : ChickN

On a recensé 81 péniches amarrées sur les berges de la Marne. Pour procéder à la surveillance de chaque péniche, il faut prévoir 6 policiers qui vont se relayer par équipe de 2 toutes les 4 heures. (pour une équipe: 4 heure de veille suivies de 8 heures de repos et remplacée pendant 4 heures par une 2^ème équipe, elle-même remplacée par la 3^ème équipe et puis à nouveau la 1^ère équipe...)
On ne dispose que de 40 policiers à placer sur cette enquête.
Si on veut surveiller chaque péniche pendant une durée totale de 48h (afin de voir le mode de vie de leur habitant, après on la laisse de coté)
INDIQUER QUELLE SERAIT LA DURÉE DE SURVEILLANCE TOTALE A PRÉVOIR POUR AVOIR UN RAPPORT SUR L’ACTIVITÉ DE CHAQUE PÉNICHE SUR UNE DURÉE DE 48H LE PLUS RAPIDEMENT POSSIBLE

Bonne chance

ChickN

Dis, tu n’essaierais pas de nous faire faire ton DM en douce, bien sûr ?

Meme pas, je fais ca pour voir si vous arrivez a resoudre ce petit casse tete... Apres libre a vous de pensez ce que vous voulez

Les 48h de surveillance doivent être contigües ou pas ?
(sinon en faisant travailler les policiers le plus possible on surveille 20 péniches en 6 jours, donc les 81 en 24 jours et 48h, mais seules 73 d'entre elles sont surveillées pendant 48h d'un seul bloc... ou même éventuellement aucune).

Les 48 heures sont effectivement contigu...
En gros on surveille un peniche 48 heures pui on la laisse de coter...

C'est marrant, avec 48h contigües je trouve aussi 26 jours. Comme quoi ça ne change rien, les heures perdues de ci de là par les policiers ponctuellement désoeuvrés dans ce dernier cas sont compensées par toutes celles perdues dans les dernières 48h par les 34 policiers qui n'ont rien à faire dans le cas où on fait une répartition naïve du travail, et où on ne tient pas compte de la nécessité de contigüité. C'est génial !
Par contre c'est nettement plus pénible de trouver la bonne répartition... À moins qu'il n'y ait un calcul plus simple que celui qui consiste à écrire un programme qui trouve la solution?

Peut etre un programme serait la bonne solution

Ben, donc, comme je disais, mon programme me donne pour solution quelque chose qu'on pourrait mettre sous forme de diagramme de cette sorte :

La première colonne de chiffres sont des numéros de lignes, il ne faut pas y faire attention
 (si je savais comment les enlever je le ferais). La seconde est le nombre d\'heures passées 
depuis le début, elles augmentent par tranches de quatre. La dernière est le nombre de poli-
ciers inactifs (ni en surveillance, ni en repos) à la fin des quatre heures.

Les croix marquent les péniches qui sont en train d'êtres surveillées, et les numéros des
péniches sont inscrits en haut.


         |123456789111111111122222222223333333333444444444455555555556666666666777777777788
         |         012345678901234567890123456789012345678901234567890123456789012345678901
---------|---------------------------------------------------------------------------------
  0    28|xxxxxx                                                                           
  4    16|xxxxxx                                                                           
  8     4|xxxxxx                                                                           
 12     4|xxxxxx                                                                           
 16     4|xxxxxx                                                                           
 20     4|xxxxxx                                                                           
 24     4|xxxxxx                                                                           
 28     4|xxxxxx                                                                           
 32     4|xxxxxx                                                                           
 36     4|xxxxxx                                                                           
 40     2|xxxxxxx                                                                          
 44     0|xxxxxxx                                                                          
 48     0|      xxxxxx                                                                     
 52     2|      xxxxxx                                                                     
 56     4|      xxxxxx                                                                     
 60     4|      xxxxxx                                                                     
 64     4|      xxxxxx                                                                     
 68     4|      xxxxxx                                                                     
 72     4|      xxxxxx                                                                     
 76     4|      xxxxxx                                                                     
 80     2|      xxxxxxx                                                                    
 84     0|      xxxxxxx                                                                    
 88     0|       xxxxxx                                                                    
 92     0|       xxxxxxx                                                                   
 96     2|            xxxxxx                                                               
100     2|            xxxxxx                                                               
104     4|            xxxxxx                                                               
108     4|            xxxxxx                                                               
112     4|            xxxxxx                                                               
116     4|            xxxxxx                                                               
120     2|            xxxxxxx                                                              
124     0|            xxxxxxx                                                              
128     0|             xxxxxx                                                              
132     0|             xxxxxxx                                                             
136     0|             xxxxxxx                                                             
140     0|              xxxxxx                                                             
144     2|                  xxxxxx                                                         
148     4|                  xxxxxx                                                         
152     4|                  xxxxxx                                                         
156     4|                  xxxxxx                                                         
160     2|                  xxxxxxx                                                        
164     0|                  xxxxxxx                                                        
168     0|                   xxxxxx                                                        
172     0|                   xxxxxxx                                                       
176     0|                   xxxxxxx                                                       
180     0|                    xxxxxx                                                       
184     0|                    xxxxxxx                                                      
188     0|                    xxxxxxx                                                      
192     0|                        xxxxxx                                                   
196     2|                        xxxxxx                                                   
200     2|                        xxxxxxx                                                  
204     0|                        xxxxxxx                                                  
208     0|                         xxxxxx                                                  
212     0|                         xxxxxxx                                                 
216     0|                         xxxxxxx                                                 
220     0|                          xxxxxx                                                 
224     0|                          xxxxxxx                                                
228     0|                          xxxxxxx                                                
232     0|                           xxxxxx                                                
236     0|                           xxxxxxx                                               
240     2|                              xxxxxx                                             
244     0|                              xxxxxxx                                            
248     2|                               xxxxxx                                            
252     0|                               xxxxxxx                                           
256     0|                               xxxxxxx                                           
260     0|                                xxxxxx                                           
264     0|                                xxxxxxx                                          
268     0|                                xxxxxxx                                          
272     0|                                 xxxxxx                                          
276     0|                                 xxxxxxx                                         
280     0|                                 xxxxxxx                                         
284     0|                                  xxxxxx                                         
288     0|                                    xxxxxxx                                      
292     2|                                     xxxxxx                                      
296     0|                                     xxxxxxx                                     
300     2|                                      xxxxxx                                     
304     0|                                      xxxxxxx                                    
308     0|                                      xxxxxxx                                    
312     0|                                       xxxxxx                                    
316     0|                                       xxxxxxx                                   
320     0|                                       xxxxxxx                                   
324     0|                                        xxxxxx                                   
328     0|                                        xxxxxxx                                  
332     0|                                        xxxxxxx                                  
336     0|                                           xxxxxx                                
340     0|                                           xxxxxxx                               
344     2|                                            xxxxxx                               
348     0|                                            xxxxxxx                              
352     2|                                             xxxxxx                              
356     0|                                             xxxxxxx                             
360     0|                                             xxxxxxx                             
364     0|                                              xxxxxx                             
368     0|                                              xxxxxxx                            
372     0|                                              xxxxxxx                            
376     0|                                               xxxxxx                            
380     0|                                               xxxxxxx                           
384     0|                                                 xxxxxxx                         
388     0|                                                  xxxxxx                         
392     0|                                                  xxxxxxx                        
396     2|                                                   xxxxxx                        
400     0|                                                   xxxxxxx                       
404     2|                                                    xxxxxx                       
408     0|                                                    xxxxxxx                      
412     0|                                                    xxxxxxx                      
416     0|                                                     xxxxxx                      
420     0|                                                     xxxxxxx                     
424     0|                                                     xxxxxxx                     
428     0|                                                      xxxxxx                     
432     0|                                                        xxxxxxx                  
436     0|                                                        xxxxxxx                  
440     0|                                                         xxxxxx                  
444     0|                                                         xxxxxxx                 
448     2|                                                          xxxxxx                 
452     0|                                                          xxxxxxx                
456     2|                                                           xxxxxx                
460     0|                                                           xxxxxxx               
464     0|                                                           xxxxxxx               
468     0|                                                            xxxxxx               
472     0|                                                            xxxxxxx              
476     0|                                                            xxxxxxx              
480     0|                                                               xxxxxx            
484     0|                                                               xxxxxxx           
488     0|                                                               xxxxxxx           
492     0|                                                                xxxxxx           
496     0|                                                                xxxxxxx          
500     2|                                                                 xxxxxx          
504     0|                                                                 xxxxxxx         
508     2|                                                                  xxxxxx         
512     0|                                                                  xxxxxxx        
516     0|                                                                  xxxxxxx        
520     0|                                                                   xxxxxx        
524     0|                                                                   xxxxxxx       
528     0|                                                                     xxxxxxx     
532     0|                                                                      xxxxxx     
536     0|                                                                      xxxxxxx    
540     0|                                                                      xxxxxxx    
544     0|                                                                       xxxxxx    
548     0|                                                                       xxxxxxx   
552     2|                                                                        xxxxxx   
556     0|                                                                        xxxxxxx  
560     2|                                                                         xxxxxx  
564     0|                                                                         xxxxxxx 
568     0|                                                                         xxxxxxx 
572     0|                                                                          xxxxxx 
576     4|                                                                            xxxxx
580     8|                                                                            xxxxx
584    12|                                                                             xxxx
588    14|                                                                             xxxx
592    16|                                                                             xxxx
596    18|                                                                              xxx
600    20|                                                                              xxx
604    24|                                                                               xx
608    26|                                                                               xx
612    30|                                                                                x
616    32|                                                                                x
620    34|                                                                                x

Etant donné que tu t'es donner beaucoup de mal est que tu es le seul a avoir poster sur ce topic je le ferme
PS: Peut tu me faire parvenir ton code Python par MP pour que j'analyse ton algorythme STP. Merci d'avance

Bah, écoute, non, je ne peux pas. D'abord parce que je l'ai fait en Caml (j'ai choisi python pour le diagramme solution parce que je trouvais la coloration un brin plus lisible que le texte tout en noir), et ensuite parce que ça n'a rien d'intéressant. Tu as la solution et tu as l'idée de l'algorithme : si tu peux prévoir 8h à l'avance que la surveillance d'une péniche va se finir et que tu as deux équipes de policiers libres, tu as intérêt à commencer la surveillance d'une nouvelle péniche pour gagner du temps ; et si tu n'as qu'une seule équipe de policiers libres, tu as intérêt à commencer la surveillance d'une nouvelle péniche 4h avant qu'une autre finisse. Ainsi tu minimises le temps où tes policiers ne font rien.
Mais le détail de l'implémentation n'a aucun intérêt.

Pas de souci
Bonne continuation...

ChickN