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:
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
Voilà le jeu de test que j'utilise :
Pas forcément très représentatif car il n'a aucune valeur >= 15 alors que cela peut se présenter.Code:
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
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.
