[VBA] Algo sac a dos 1D

Bonjour,
étant débutant en programmation, je fais actuellement un programme pour le problème du sac à dos 1D, également connu sous le nom de Bin Packing 1D, avec lequel j'ai un problème ...

Ce programme consiste a trier des valeurs (de n'importe quel type) de façon à avoir un gain de place ou de matière sur le principe du Bin Packing 1D.

Exemple:
Je dispose de données informatiques de différentes tailles que je veux mettre sur CD, j'essai donc d'optimiser la place afin d'utiliser le moins de CD possible:

Données de 500mo, 400mo , 300mo et 100mo.
Place sur CD 700mo.

Il est donc logique de placer 400 et 300 ensemble pour remplir un CD et 500 et 100 ensemble pour le second.
Dans ce cas j'utilise 2 cd, pour les autres solutions au moins 3.


Voir également https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_bin_packing
et https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos

Dans mon cas, je créé ce programme pour optimiser la découpe de barre (comme en menuiserie).

J'ai des barres standard de 2500mm et j'aimerai les découper en barres de différentes longueurs (exemple 1000, 1345, 537 ,886... dans des quantités plus importantes (>1000)) en utilisant le moins de barres standard possible.

J'utilise donc la méthode Deacrising First Fit (qui consiste a trier les longueurs dans l'ordre décroissant puis de les ranger au fur a mesure dans la 1ere barre ou il y a de la place).

En reprenant l'exemple du CD.

Dans l'ordre décroissant j'ai 500,400,300,100

CD1 je place 500.
400 ne rentre plus de CD1 (400+500>700), je créé donc un CD2 pour le placer dedans.
300 ne rentre pas dans CD1, 300 rentre dans CD2. On rajoute 300 au CD2.
100 rentre dans CD1, on le rajoute au CD1.

J'utilise également la méthode du Deacrising Best Fit qui est plus précise, mais je n'ai pas de réèl intérêt à prendre ce dernier car mon programme est utilisé pour des grandes séries de barres (plus de 1000 fois la même valeur).
Je trouve donc le même résultat qu'en Next Fit mais en un temps beaucoup plus important.

Mon problème
Mon problème est que je ne trouve pas , dans de rare cas, une solution suffisament proche de l'optimale.

Exemple: j'ai des barres de 2500, j'aimerai 10 barres de 1000 et 20 de 700.

L'optimale est d'avoir 10 barres de 2500 qu'on découpe en 1000+700+700 = 2400.

Mais en Decreasing First Fit ou Next Fit je me retrouve avec 5 barres de 1000+1000=2000 et 6 barres de 700+700+700 = 2100 et 1 barre de 700+700=1400.

Soit un surplus de 20% (12 barres au lieu de 10).

Je sais que ma méthode est heuristique (permet de trouver rapidement un résultat approché de l'optimal), mais je sais également qu'il est possible d'avoir un tri plus approché dans le cas ci dessus, seulement je ne sais pas comment faire.

Pouvez vous m'aider?

Merci