Trouver la meilleur note possible ?
Salut OLGone,
Salut l'équipe,
j'arrive également au résultat de 143,1 pour L10 = 120.
Je peaufine mon code et je reviens!
A+
bonsoir,
même résultat que bsalv avec 143.8 pour 120 de L10 sur 4 joueurs, 16439 combinaisons examinées.
| Nom | L10 | Total |
| Karl-Anthony Towns | 40 | 44.05 |
| Michael Porter Jr. | 27 | 33.86 |
| Walker Kessler | 27 | 33.71 |
| Mikal Bridges | 26 | 32.18 |
| TOTAL | 120 | 143.8 |
Re,
un double-clic sur la feuille démarre la macro.
Curieux de voir ça avec 500 lignes!!
tTab = [DATAS].Cells
'
For x = 1 To UBound(tTab, 1) - 3
dT1 = tTab(x, 4)
iL1 = tTab(x, 3)
For y = x + 1 To UBound(tTab, 1) - 2
iL2 = iL1
dT2 = dT1
If iL1 + tTab(y, 3) <= 120 Then
dT2 = dT2 + tTab(y, 4)
iL2 = iL2 + tTab(y, 3)
For Z = y + 1 To UBound(tTab, 1) - 1
iL3 = iL2
dT3 = dT2
If iL2 + tTab(Z, 3) <= 120 Then
dT3 = dT3 + tTab(Z, 4)
iL3 = iL3 + tTab(Z, 3)
For w = Z + 1 To UBound(tTab, 1)
If iL3 + tTab(w, 3) <= 120 Then
dT4 = dT3 + tTab(w, 4)
iL4 = iL3 + tTab(w, 3)
Else
If dT4 >= dBest Then
tData(0, 0) = iL4
tData(0, 1) = dT4
tData(0, 2) = tTab(x, 2)
tData(0, 3) = tTab(y, 2)
tData(0, 4) = tTab(Z, 2)
tData(0, 5) = tTab(w - 1, 2)
dBest = dT4
End If
End If
Next
Else
Exit For
End If
Next
Else
Exit For
End If
Next
Next
Range("I10:N10").Value = tDataA+
Re-salut les cracks,
ouf, je rejoins les 143,8 et L10 = 120 !
Faudra que je turbine encore car je comptabilise près de 60.000 combinaisons pour y arriver!
A+
EDIT
Oups, problème sur le fichier.. Je le remets.
Sauf erreur, je suis descendu à +- 9000 combinaisons!
Bonsoir à tous,
Pour revenir sur la remarque de Nain porte koi, est-ce que ce problème ne ressemble pas au "coin change problem" traité via le solveur.
Voir le fichier joint :
klin89
Bonsoir à tous,
Pour le fun j'ai fait une version pour Google Sheets
Je poste ça là pour les éventuels intéressés :
function test() {
const tab = SpreadsheetApp.getActive().getSheetByName('Feuille 1').getRange('B2:D43').getValues();
const nb = tab.length;
const tabResultats = [];
for (let i = 0; i < nb; i++) {
for (let j = 0; j < nb; j++) {
if (j >= i) break;
for (let k = 0; k < nb; k++) {
if (k >= j) break;
for (let l = 0; l < nb; l++) {
if (l >= k) break;
if (tab[i][1] + tab[j][1] + tab[k][1] + tab[l][1] <= 120)
tabResultats.push([i, j, k, l, tab[i][2] + tab[j][2] + tab[k][2] + tab[l][2]]);
}
}
}
}
const resultat = tabResultats.sort((a, b) => b[4] - a[4])[0].map(t => tab[t] ?? ['TOTAL = ' + t]);
console.log(resultat);
}Résultat :
Le même code dans une version plus courte (résultat identique) :
function test() {
const d = SpreadsheetApp.getActive().getSheetByName('Feuille 1').getRange('B2:D43').getValues(), r = [];
for (let i = 0; i < d.length; i++)
for (let j = 0; j < i; j++)
for (let k = 0; k < j; k++)
for (let l = 0; l < k; l++)
d[i][1] + d[j][1] + d[k][1] + d[l][1] <= 120 && r.push([i, j, k, l, d[i][2] + d[j][2] + d[k][2] + d[l][2]]);
console.log(r.sort((a, b) => b[4] - a[4])[0].map(t => d[t] ?? ['TOTAL = ' + t]));
}Bonjour tout le monde,
Codage et reportage foot ne faisant pas bon ménage, j'ai repris le travail ce matin, mieux concentré.
Toujours un double-clic sur la feuille 'Datas' pour un résultat en 'Best'.
A+
re,
la feuille "Solver" = la solution avec solver quasi instantément. Mon experience me dit que solver traite bien ce genre de problèmes jusqu'à 50 variables, donc ici avec 42, okay. Mais si on répète cela avec 100 lignes, solver se perd dans les branches ... .
Comme on voulait traiter jusqu'à 500 éléments ...
pour la solution de @curulis57, voir les calculations dans la plage N514, pour ces 500 lignes.
là, je calcule les lignes à partir d'où une meilleur solution n'est plus possible, je ne sais pas si cela diminue le nombre de tentatives de la macro ??? A premiere vue, cela donne une réduction de 30%, mais je n'ai aucune idée de la réduction déjà réalisée avec ces lignes "if ... then exit for"
For x = 1 To UBound(tTab, 1) - 3 >>>>>>> For x = 1 To 135
For y = x + 1 To UBound(tTab, 1) - 2
If tTab(x, 3) + tTab(y, 3) > 120 Then Exit For
For Z = y + 1 To UBound(tTab, 1) - 1
If tTab(x, 3) + tTab(y, 3) + tTab(Z, 3) > 120 Then Exit For For w = Z + 1 To UBound(tTab, 1) >>>>>>>>>>> For w = application.max(153,Z + 1) To UBound(tTab, 1)
ma solution de hier 9:57 donnait une "solution" pour 500 lignes en 30 secondes mais il y a une possibilité que cette solution n'était pas la "meilleur", mais si on doit attendre plusieurs heures pour cela ...
Bonjour à tous,
Bravo à Curulis et Sébastien qui ont résolu le problème du temps d’exécution. Je réfléchissais hier soir à un algo en triant la liste et je vois que c’est la solution qu’a choisie Curulis, je pense que c’est pour VBA la meilleure approche. Il faudrait tester sur de vrais grands échantillons de données les différents algos ce serait intéressant.
Dommage, on n’a pas eu de proposition powerquery…
Bonne journée à tous.
Salut les as,
je vois que ce truc passionne! Pas étonnant!
Je suis aussi impatient que vous de voir ce que ça donnerait avec 500 lignes de datas.
Evidemment, de 100.000 combinaisons actuellement, on passerait à 2.500.000.000 !!
Peut-être en lançant le calcul avant le dodo ?!
Salut BsAlv, l'équipe,
en "créant" 500 lignes sur base de l'existant et en bidouillant au hasard les L10 et les points des uns et des autres, je tombe effectivement sur une douzaine de secondes pour +- 14.000.000 de combinaisons testées.
Pas trop mal, finalement!
bonjour à tous,
avec 500 données au hasard, (la vitesse et le nombre de combinaisons examinées dépend fortement des données, cela varie de moins d'une seconde à plusieurs minutes (voire heures)...
edit : ajout commentaires + correction bug
impressionat aussi h2so4, il est recursif mais je ne l'ai pas encore bien lu ...
Bonjour à tous,
Je pense que l’op, quand il mentionnait les “differences” parlait de trier les joueurs en fonction de leur écart par rapport à leur “L10”. C’est une solution qui me semble pertinente puisque l’objectif initial était quand meme de récompenser les “meilleurs joueurs”, et en supposant que L10 représente leur score précédent/moyen, on favorise ainsi les joueurs ayant le mieux performé.
Ainsi il suffirait pour résoudre le problème de chercher le meilleur joueur par score L10 (beaucoup de joueurs partagent le meme), puis de regarder les combinaisons possibles telles que la somme des L10 de 4 joueurs <= 120. Puis récupérer dans cette liste le groupe qui obtient le meilleur score Daily et le meilleur score L10.
Etant donné que la quantité de L10 n’augmente pas avec le nombre de joueurs (ou très peu), on reste sur un temps d’exécution constant.
En plus en structurant les données de la manière suivante : L10 -> score (liste de L10 donnant le score), on peut trier la liste et réduire grandement le calcul des permutations car en la parcourant triée on peut éviter tous les doubles checks.
On peut retrouver ensuite chaque joueur à l’aide de son doublon [L10, scoreDaily].
Sur l’exemple de Bart avec 500 participants on trouve 45 “L10” uniques, donc seulement combin(45;4)=150 000 combinaisons à traiter.
Cependant encore à l’aide du tri on peut s’arreter dès que l’on voit que les nouvelles combinaisons offrent des résultats (somme des L10) moins bons, et donc réduire grandement ce nombre. J’essaierai de faire un algo. J’avais quasiment réussi avec uniquement des formules XL mais je bloque sur la génération des permutations.
--
L’idée étant de se ramener au problème que vous avez déjà résolu, en filtrant d’abord une pool des meilleurs joueurs de taille quasi constante, et ensuite traiter le problème.
@saboh12617,
à partir de la colonne AA, on a 45 poids uniques de L10 et leur nombre dans la colonne AB, puis les "Daily" descendant à partir de la colonne AC.
Maintenant il faut faire des permutations ou lieu de combinaisons, alors il y en a 3.576.000 !!!!!
Vue la vitesse de h2so4 et curulis57, je ne pense pas que c'est une bonne idée.
PS. il faut attendre la réponse de l'op pour savoir si on doit utiliser la colonne "daily" ou la colonne "diff"
Je voulais permuter sur les 45 poids, en prenant pour chaque poids le meilleur Daily.
Daily et diff sont la même chose car il me semble que Diff = Daily-L10.
Donc prendre le meilleur Daily par L10 revient a prendre le meilleur diff.
Ensuite pour les permutations , inutile de toutes les examiner. Seules les plus proches du score voulu (120) sont intéressantes. Donc en triant les L10 du plus grand au plus petit on évite de permuter les petites valeurs inutilement. Il me semble que c'est ce que faisait curulis. Quand j'ai quelque chose je le partage.
une solution avec "Opensolver" (Solver ne le trouvait pas)
Bonsoir BsAlv, Saboh,
...complètement dépassé par vos explications!
Ce que j'obtiens avec ma macro, c'est +-2 minutes de traitement pour 1000 lignes
re,
@Curulis57,
ce n'est pas tout à fait bête, voir PJ, 500 lignes et en colonne H, toutes les lignes à partir du 5eme "large" valeur du même L10 est "0".
Comme ça, on n'a que 180 (36%) des 500 lignes dans la matrice tTab de votre macro. C'est pourquoi la macro ne prend que 0.95 (10%) sec au lieu de 10 sec pour toutes les 500 lignes. Donc vos 2 minutes pour 1.000 lignes ne sera que 12 sec (dépendant de la composition des données) avec cette ajustement.
ps. cela n'enlève rien à ma bonne impression de la rapidité de votre solution