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

Question

^{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.

Answer 1

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