12
$\begingroup$

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³.

PD by 1212eins@pixabay.com

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.
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Dec 14 '16 at 23:44
  • $\begingroup$ My older Christmas questions on Santa-routing and on cookie tiling are both at least partially open, too! $\endgroup$ – Raphael Dec 15 '16 at 0:04
  • $\begingroup$ Bah! ... Humbug! $\endgroup$ – Rick Decker Dec 15 '16 at 1:50
  • 2
    $\begingroup$ 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}$). $\endgroup$ – Manlio Dec 15 '16 at 9:11
1
$\begingroup$

After quickly looking at this question, I believe Rupert's extra knowledge of each child's {behavior, max value present} will not always make Santa's job easier. Santa will still need to perform a 0/1 knapsack to fill the bags and a Hungarian algorithm as well to maximize the happiness each capitalist child receives on Christmas morning. A simple case where it would make Santa's job quite simple is if every child Santa was considering didn't publish a paper and instead played video games all year received a zero from Rupert (each child would get coal).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.