Est-il plus facile d'emballer un sac de cadeaux pour Rupert que pour le Père Noël?

^{Ou: Avons-nous besoin de Rupert pour obtenir des cadeaux?}

Mis à part les problèmes de routage , le Père Noël est confronté au problème suivant (plusieurs fois):

Étant donné un sac d'une capacité¹ $C$ et un ensemble de cadeaux $\{p_1, \dots, p_n\}$ , chacun de taille $s_i$ , il veut faire plaisir aux enfants $\{c_1, \dots, c_k\}$ . Il sait de toutes les listes de souhaits que les valeurs de l' enfant $c_j$ présentent $p_i$ exactement $v_{i,j} \in \mathbb{Q}_{\geq 0}$ beaucoup.

Quels ensembles (disjoints deux à deux) de cadeaux $I_j \subseteq [1..n]$ choisir pour chaque enfant afin que tout rentre, c'est-à-dire

$\qquad\displaystyle \sum_{j \in [1..k]} \sum_{i \in I_j} s_i \leq C$,

et le plus de bonheur possible s'ensuit², c'est-à-dire

$\qquad\displaystyle \max! \sum_{j \in [1..k]} \sum_{i \in I_j} v_{i,j}$

Ce n'est clairement pas plus facile que le Bin Bining ou le Knapsack, donc le pauvre Père Noël devra peut-être passer beaucoup de temps à emballer des sacs³.

Maintenant, comme nous le savons, son assistant Rupert ne donne pas aussi inconditionnellement. Il a des connaissances sur , la valeur maximale que l'enfant peut recevoir en fonction de son comportement au cours de l'année; c'est-à-dire qu'il ajoute une contrainte supplémentaire$V_j$$c_j$

$\qquad\displaystyle \forall j \in [1..k].\ \sum_{i \in I_j} v_{i,j} \leq V_j$ .

Est-ce que cela facilite le problème de l'emballage des sacs? Si ce n'est pas toujours le cas, dans quelles conditions?

1. Si le diamètre c himinal est le facteur limitant, un cadre similaire peut être établi.
2. Ne nous préoccupons pas d'équité et d'autres idées ridicules.
3. Par conséquent, un seul Noël par an. QED

Après avoir rapidement examiné cette question, je crois que les connaissances supplémentaires de Rupert sur le {comportement, la valeur maximale présente} de chaque enfant ne faciliteront pas toujours le travail du Père Noël. Le Père Noël devra toujours effectuer un sac à dos 0/1 pour remplir les sacs et un algorithme hongrois afin de maximiser le bonheur que chaque enfant capitaliste reçoit le matin de Noël. Un cas simple où cela rendrait le travail du Père Noël assez simple est si chaque enfant envisagé par le Père Noël ne publiait pas de papier et jouait à des jeux vidéo toute l'année a reçu un zéro de Rupert (chaque enfant obtiendrait du charbon).