# 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, 2016 at 23:44
• My older Christmas questions on Santa-routing and on cookie tiling are both at least partially open, too!
– Raphael
Dec 15, 2016 at 0:04
• Bah! ... Humbug! Dec 15, 2016 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}$). Dec 15, 2016 at 9:11