Problème d'emballage d'algorithme gourmand

Question

Suppose que $ A $ est l'ensemble d'objets tels que chaque objet $ x_i dans un $ a de la valeur $ w_i $. Nous souhaitons emballer ces objets en groupe, chaque pack contenant au moins $ k $ objets. Notre objectif est de minimiser la différence maximale entre la valeur maximale et minimale de chaque pack. En d'autres termes, notre objectif est de minimiser $ L $ avec la contrainte que tous les packs devraient avoir plus que $ k $ Object en eux.

$$ l = max_ {i in mathrm {packs}} Left { max_ {j in mathrm {pack} (i)} w_j - min_ {k in mathrm {pack} (i )} w_k droite }. $$

Par exemple pour l'emballage suivant, $ L $ est $ max {(30-20, 120 - 100)} = 20 $. $$[20, 30] \;\; [100,110,120]$$

Je me demandais s'il y avait un algorithme gourmand qui peut faire le travail.