Empacotar um saco de presentes é mais fácil para Rupert do que para o Papai Noel?

^{Ou: precisamos de Rupert para receber presentes?}

Questões de roteamento à parte, o Papai Noel enfrenta o seguinte problema (muitas e muitas vezes):

Dado um saco com capacity¹ $C$ e um conjunto de presentes $\{p_1, \dots, p_n\}$ , cada um com tamanho $s_i$ , ele quer fazer as crianças $\{c_1, \dots, c_k\}$ feliz. Ele sabe de todas as listas do desejo que a criança $c_j$ valores presentes $p_i$ exatamente $v_{i,j} \in \mathbb{Q}_{\geq 0}$ muito.

Quais conjuntos de presentes (separados por pares) para escolher para cada criança para que tudo se encaixa, ou seja,$I_j \subseteq [1..n]$

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

e o máximo de felicidade possível², isto é,

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

Claramente, isso não é mais fácil do que a Bin Packing ou a mochila, então o pobre Papai Noel pode ter que gastar muito tempo fazendo as malas³.

Agora, como sabemos, seu assistente Rupert não dá tão incondicionalmente. Ele tem conhecimento sobre , o valor máximo filho c $V_j$$c_j$ pode receber com base no comportamento durante o ano; isto é, ele adiciona uma restrição adicional

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

Isso facilita o problema de fazer as malas? Se não sempre, então em que condições?

1. Se o c diâmetro himney é o fator limitante, um quadro semelhante pode ser estabelecida.
2. Não vamos nos preocupar com justiça e outras idéias ridículas.
3. Portanto, apenas um Natal por ano. QED

Depois de analisar rapidamente essa pergunta, acredito que o conhecimento extra de Rupert sobre o comportamento de cada criança (comportamento, valor máximo presente) nem sempre facilitará o trabalho do Papai Noel. O Papai Noel ainda precisará executar uma mochila 0/1 para encher as malas e um algoritmo húngaro, além de maximizar a felicidade que cada criança capitalista recebe na manhã de Natal. Um caso simples em que isso tornaria o trabalho de Papai Noel bastante simples é se todas as crianças que Papai Noel considerasse não publicassem um jornal e, em vez disso, jogassem videogame durante todo o ano recebessem zero de Rupert (cada criança receberia carvão).