trouver un sous-ensemble de nombres qui correspondent le mieux à une somme

Question

Je cherche une technique ou un algorithme qui me donnera un sous-ensemble d'entiers d'un ensemble donné qui, une fois additionnés, correspondent le plus étroitement à un nombre cible donné.

J'ai une vidéo de musique et je veux la vidéo pour 248 images. J'ai un ensemble de clips de différentes longueurs, tous moins de 248. Je voudrais un sous-ensemble de ceux qui sont les plus proches de 248 lorsque leurs longueurs sont additionnées.

Y at-il quelque chose sur la ligne de commande linux que je peux utiliser pour faire cela?

Answer 1

Ye Olde Bin Packing Problem et bizarrement je ne peux pas penser à une implémentation standard.