# Is packing a bag of presents easier for Rupert than Santa?

Or: Do we need Rupert in order to get presents at all?

Routing issues aside, Santa faces the following problem (many, many times over):

Given a bag with capacity¹ $C$ and a set of presents $\{p_1, \dots, p_n\}$, each with size $s_i$, he wants to make children $\{c_1, \dots, c_k\}$ happy. He knows from all the wish lists that child $c_j$ values present $p_i$ exactly $v_{i,j} \in \mathbb{Q}_{\geq 0}$ much.

Which (pairwise disjoint) sets of presents $I_j \subseteq [1..n]$ to pick for each child so that everything fits, i.e.

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

and as much happiness as possible ensues², i.e.

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

This is clearly not easier than Bin Packing or Knapsack, so poor Santa may have to spend a long time packing bags³.

Now, as we know, his assistant Rupert does not give as unconditionally. He has knowledge about $V_j$, the maximum value child $c_j$ may receive based on behaviour during the year; that is, he adds an additional constraint

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

Does that make the problem of packing bags easier? If not always, then under which conditions?

1. If the chimney diameter is the limiting factor, a similar framework can be established.
2. Let's not concern ourselves with fairness and other ridiculuous ideas.
3. Hence, only one Christmas per year. Q.E.D.
• Everybody who wants to give to fellow users, add a bounty once that's possible! Correct and understandable answers who also conjure the spirit of the holidays the most will be eligible! – Raphael Dec 14 '16 at 23:44
• My older Christmas questions on Santa-routing and on cookie tiling are both at least partially open, too! – Raphael Dec 15 '16 at 0:04
• Bah! ... Humbug! – Rick Decker Dec 15 '16 at 1:50
• A couple of trivial comments: the problem cannot always be easier (just pick $V_j \ge \sum_{i\in I_j} v_{i,j}$) but there is at least one case in which it is (set all $V_j=0$ except $V_1$, which is set to $\min_i v_{i,1}$). – Manlio Dec 15 '16 at 9:11