Bonjour
Je suis programmeur php et mon patron me demande sur notre application de logistique d'optimiser le nombre de colis.
Il s'agit à partir d'un tableau associatif Ref->Qté de faire le maximum de colis, chaque colis contenant exactement 15 articles mais avec un maximum de 3 références.

J'ai écrit un algo en php qui fonctionne, mais il part des valeurs maximales en reclassant chaque fois le tableau en ordre décroissant des quantités et ce n'est pas la bonne approche: sur le jeu de test, il fait 7 cartons alors qu'il y a moyen d'en tirer au moins 8.

Ma fonction :
Code php : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
function build_carton($tableau) {
        $arr_result = array();//tableau résultat
 
        do{
			//tri en ordre décroissant des quantités le tableau en gardant les clés 
			arsort($tableau);
 
			$cpt = 0; $tot3prem = 0;
			foreach ($tableau as $key => $val) {//on fait la somme des 3 premiers
				$cpt++;
				$tot3prem += $val;
				if($cpt == 3) break;
			}
                        echo 'total 3 prem '.$tot3prem.'<br />';
			if ($tot3prem >= 15) {//il y en a assez pour faire un carton
				$tot_carton = 0;
				$arr_carton = array();
				echo 'Nouveau carton : <br />';
				foreach ($tableau as $key => &$value){
					$qte = $value;
					$qte_utile = 15 - $tot_carton;
					if($qte > $qte_utile) $qte = $qte_utile;
					$tableau[$key] = $value - $qte;
					$tot_carton += $
					echo  $key . ' Quantité : '.$qte.' Reste : ' . $tableau[$key] .br();
					$arr_carton[$key] = $qte;
					if($tot_carton == 15){
                                            break 1;
                                        }
				}
				$arr_result[] = $arr_carton;
			}else{
				echo "pas assez d'articles pour faire un carton";
			}
        }while ($tot3prem >= 15);
        return $arr_result;
    }

Voilà le jeu de test que j'utilise :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
3607868152642;5
3607868152635;6
3607868152628;6
3607868298845;6
3607868298821;6
3607868298838;6
3607868152246;4
3607868152239;4
3607868152222;4
3607868152215;4
3607868152284;4
3607868152277;4
3607868152260;4
3607868152253;4
3607868152130;4
3607868152147;5
3607868152154;4
3607868152161;3
3607868298814;4
3607868152611;4
3607867486274;1
3607867832286;1
3607867230266;1
3607867591442;1
3607867416684;1
3607867352203;1
3607867891337;3
3607867892228;2
3607867892242;3
3607867892181;3
3607867893034;5
3607867893027;5
3607867893010;3
3607867911189;2
3607867911172;3
3607867911165;2
3607867895731;2
3607867891344;1
3607867914302;4
3607867912261;3
3607867892235;3
3607867914296;2
3607867896660;2
3607867921942;4
3607867911196;1
3607867895724;2
3607867895717;1
3607867920310;2
3607867896615;2
3607867896639;2
3607867896646;1
3607867920303;2
3607867896622;3
3607867896585;3
3607867896578;3
3607867920297;2
3607867896561;2
3607867896592;2
3607867896691;2
3607867891320;1
3607867896684;3
3607867896677;2
3607867909483;3
3607867909490;2
3607867909476;3
3607867909469;2
3607867909568;2
3607867909575;3
3607867909582;3
3607867909599;2
3607867914326;2
3607867912216;4
3607867912209;4
3607867914258;3
3607867920327;1
3607867914265;4
3607867912193;3
3607867914272;2
3607867912223;2
3607867892129;3
3607867892174;2
3607867892136;3
3607868084790;5
3607868084783;6
3607868084806;2
3607867892112;1
3607867912247;2
3607867912254;3
3607867914241;2
3607867912278;1
3607867931484;6
3607867931378;3
3607867931538;3
3607867931514;4
3607867894543;1
3607867894437;2
3607867894420;3
3607867894512;2
3607867894536;2
3607867894529;3
3607867894444;1
3607867894413;1
3607867914319;5
3607867340095;4
3607867340088;4
3607867912308;2
3607867912322;1
3607867912315;3
3607867912292;1
3607867385362;2
3607867536719;9
3607867536726;8
3607867545988;5
3607867390861;1
3607867390793;6
3607867921959;2
3607867475254;7
3607867475230;5
3607867475223;5
Pas forcément très représentatif car il n'a aucune valeur >= 15 alors que cela peut se présenter.
J'ai pensé utiliser l'algorithme du simplexe mais je ne pense pas qu'il soit applicable avec une série en entrée. Enfin je ne vois pas comment l'appliquer dans ce cas là.
Votre avis svp: on peut optimiser ça ou c'est du np-complet ? Me rappelle furieusement le problème du sac à dos ça.