Czy pakowanie torby prezentów jest łatwiejsze dla Ruperta niż Świętego Mikołaja?

^{Lub: Czy potrzebujemy Ruperta, aby w ogóle otrzymać prezenty?}

Pomijając problemy z routingiem, Święty Mikołaj napotyka następujący problem (wiele, wiele razy):

Biorąc pod uwagę torbę o pojemności¹ i zestaw prezentów , każdy o rozmiarze , chce uszczęśliwić dzieci . Ze wszystkich list życzeń wie, że potomne wartości prezentują dokładnie bardzo często. $C$ $\{p_1, \dots, p_n\}$ $s_i$ $\{c_1, \dots, c_k\}$ $c_j$ $p_i$ $v_{i,j} \in \mathbb{Q}_{\geq 0}$

Które (rozłączne parami) zestawy prezentów $I_j \subseteq [1..n]$ należy wybrać dla każdego dziecka, aby wszystko pasowało, tj.

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

i wynika z tego jak najwięcej szczęścia², tj

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

Nie jest to oczywiście łatwiejsze niż pakowanie pojemników lub plecak, więc biedny Święty Mikołaj może spędzać dużo czasu pakując torby3.

Teraz, jak wiemy, jego asystent Rupert nie udziela tak bezwarunkowo. Ma wiedzę na temat $V_j$ , maksymalnej wartości, jaką dziecko $c_j$ może otrzymać na podstawie zachowania w ciągu roku; to znaczy dodaje dodatkowe ograniczenie

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

Czy to ułatwia pakowanie toreb? Jeśli nie zawsze, to na jakich warunkach?

Jeżeli C Średnica himney jest czynnikiem ograniczającym, podobne ramy może być ustanowiony.
Nie przejmujmy się uczciwością i innymi śmiesznymi pomysłami.
Dlatego tylko jedno Boże Narodzenie rocznie. CO BYŁO DO OKAZANIA

— Raphael
źródło

Każdy, kto chce dać innym użytkownikom, dodaj nagrodę, gdy tylko będzie to możliwe! Poprawne i zrozumiałe odpowiedzi, który również wyczarować ducha świąt najbardziej będą się kwalifikować!

— Raphael

Moje starsze świąteczne pytania dotyczące routingu Świętego Mikołaja i układania ciasteczek są przynajmniej częściowo otwarte!

— Raphael

Bah! ... Humbug!

— Rick Decker

Kilka trywialnych komentarzy: problem nie zawsze może być łatwiejszy (wystarczy wybrać ), ale istnieje co najmniej jeden przypadek, w którym jest (ustaw wszystkie oprócz , który jest ustawiony na ).

V_{j} \geq \sum_{i \in I_{j}} v_{i, j}

$V_j \ge \sum_{i\in I_j} v_{i,j}$

V_{j} = 0

$V_j=0$

V_{1}

$V_1$

min_{i} v_{i, 1}

$\min_i v_{i,1}$

— Manlio,

Po szybkim spojrzeniu na to pytanie, wierzę, że dodatkowa wiedza Ruperta na temat zachowania każdego dziecka {zachowanie, maksymalna wartość obecna} nie zawsze ułatwi pracę Świętego Mikołaja. Święty Mikołaj nadal będzie musiał wykonać plecak 0/1, aby zapełnić torby, a także węgierski algorytm, aby zmaksymalizować szczęście, jakie każde kapitalistyczne dziecko otrzymuje w Boże Narodzenie rano. Prostym przypadkiem, w którym sprawiłoby, że praca Świętego Mikołaja byłaby bardzo prosta, gdyby każde rozważane przez niego dziecko nie opublikowało gazety i zamiast tego grało w gry wideo przez cały rok otrzymywało zero od Ruperta (każde dziecko dostawałoby węgiel).

— Logan Leland
źródło