Упаковать сумку подарков для Руперта легче, чем для Санты?

^{Или: нам нужен Руперт, чтобы вообще получать подарки?}

Помимо вопросов маршрутизации , Санта сталкивается со следующей проблемой (много-много раз):

Имея сумку вместимостью ¹ $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}$ .

Какие (попарно непересекающиеся) наборы подарков $I_j \subseteq [1..n]$ выбрать для каждого ребенка, чтобы все подходило, т.е.

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

и как можно больше счастья2, т.е.

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

Это явно не легче, чем упаковка в бен или рюкзак, так что бедному Санте, возможно, придется долго паковать сумки ³.

Сейчас, как известно, его помощник Руперт не дает так безоговорочно. Он знает о , максимальном значении, которое ребенок может получить, основываясь на поведении в течение года; то есть он добавляет дополнительное ограничение $V_j$ $c_j$

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

Это облегчает проблему упаковки мешков? Если не всегда, то при каких условиях?

Если с диаметром himney является ограничивающим фактором, может быть создана аналогичная структура.
Давайте не будем заботиться о справедливости и других нелепых идеях.
Следовательно, только одно Рождество в год. QED

algorithms complexity-theory optimization packing Рафаэль
источник

Все, кто хочет дать другим пользователям, добавьте награду, как только это возможно! Правильные и понятные ответы, которые также вызывают дух праздников, будут иметь право!

Рафаэль

Мои старые рождественские вопросы о Санта-маршрутизации и об использовании файлов cookie , по крайней мере, частично открыты!

Рафаэль

Ба! ... Обмани!

Рик Декер

Пара тривиальных комментариев: проблема не всегда может быть проще (просто выберите ), но есть хотя бы один случай, в котором она есть (установите все кроме , который установлен в ).

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}$

Манлио

Быстро рассмотрев этот вопрос, я считаю, что дополнительные знания Руперта о {поведении, максимальном значении каждого ребенка} не всегда облегчают работу Санты. Санте все еще нужно будет выполнить рюкзак 0/1, чтобы заполнить сумки, а также венгерский алгоритм, чтобы максимизировать счастье, которое каждый капиталистический ребенок получает в рождественское утро. Простой случай, когда это делало бы работу Санты довольно простой, - это если бы каждый ребенок, которого рассматривал Санта, не публиковал газету и вместо этого играл в видеоигры весь год, получал ноль от Руперта (каждый ребенок получал уголь).

Логан Леланд
источник

Упаковать сумку подарков для Руперта легче, чем для Санты?

Ответы: