Ist es für Rupert einfacher, eine Tüte mit Geschenken zu packen als für den Weihnachtsmann?

^{Oder: Brauchen wir Rupert, um überhaupt Geschenke zu bekommen?}

Abgesehen von Routing-Problemen steht der Weihnachtsmann vor dem folgenden Problem (viele, viele Male):

Mit einer Tasche mit einer Kapazität von und einer Reihe von Geschenken , die jeweils die Größe , möchte er Kinder glücklich machen. Er weiß aus allen Wunschlisten, dass Werte genau .{ p 1 , … , p n } s i { c 1 , … , c k } c j p i v i , j ∈ Q ≥ $C$$\{p_1, \dots, p_n\}$$s_i$$\{c_1, \dots, c_k\}$$c_j$$p_i$$v_{i,j} \in \mathbb{Q}_{\geq 0}$

Welche (paarweise disjunkten) Geschenkmengen für jedes Kind auszuwählen sind, damit alles passt, d.$I_j \subseteq [1..n]$

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

und so viel Glück wie möglich folgt², dh

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

Dies ist eindeutig nicht einfacher als Mülleimer oder Rucksack, sodass der arme Weihnachtsmann möglicherweise lange Zeit damit verbringen muss, Taschen zu packen³.

Nun, wie wir wissen, gibt sein Assistent Rupert nicht so bedingungslos. Er hat Kenntnisse über , den Maximalwert, den das Kind aufgrund Verhaltens während des Jahres erhalten kann. Das heißt, er fügt eine zusätzliche Einschränkung hinzu$V_j$$c_j$

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

Erleichtert das das Packen von Taschen? Wenn nicht immer, unter welchen Bedingungen?

1. Wenn die C himney Durchmesser der limitierende Faktor ist, kann ein ähnlicher Rahmen festgelegt werden.
2. Kümmern wir uns nicht um Fairness und andere lächerliche Ideen.
3. Daher nur ein Weihnachten pro Jahr. QED

Nachdem ich mir diese Frage schnell angeschaut habe, glaube ich, dass Ruperts zusätzliches Wissen über das {Verhalten, maximaler Wert, der vorhanden ist} jedes Kindes nicht immer die Arbeit des Weihnachtsmanns erleichtern wird. Der Weihnachtsmann muss noch einen 0/1-Rucksack tragen, um die Taschen zu füllen, und einen ungarischen Algorithmus, um das Glück zu maximieren, das jedes kapitalistische Kind am Weihnachtsmorgen empfängt. Ein einfacher Fall, der die Arbeit des Weihnachtsmanns recht einfach machen würde, wäre, wenn jedes Kind, das der Weihnachtsmann in Erwägung ziehen würde, keine Zeitung veröffentlichen und stattdessen das ganze Jahr über Videospiele spielen würde, von Rupert eine Null erhalten würde (jedes Kind würde Kohle bekommen).