Максимально возможное количество людей

[main.c]

Есть набор характеристик людей $x_1, x_2, x_3$, есть правило, что нам нужно не более 30 человек с $x_1$, не более 20 с $x_2$ и не более 1 с $x_3$. При этом каждый человек должен удовлетворять 2 характеристикам одновременно. Сколько максимально возможное количество людей мы можем получить? В данном случае ответ 21, это случай, когда придут 20 человек с $x_1$ и $x_2$, и 1 человек с $x_2$ и $x_3$. Итак, это был пример, теперь эта же задача в обобщенном виде, есть $n$ характеристик $x_1, ..., x_n$, на каждую их них стоит ограничение на количество людей с соотвтетствующей характеристикой: $m_1, ..., m_n$, каково максимально возможное количество людей удовлетяворяющих одновременном $p$ характеристикам, где $p \leq n$.

[svv]

Перенумеруем характеристики так, чтобы было
$m_1\leqslant m_2\leqslant \cdots \leqslant m_{n-1}\leqslant m_n$
Далее берём первого человека и наделяем его характеристиками $m_1,\cdots,m_p$. Так же поступаем со вторым, третьим... до тех пор, пока количество людей с $m_1$ не достигнет ограничения.
Потом берём следующего человека и наделяем его характеристиками $m_2,\cdots,m_{p+1}$, пока количество людей с $m_2$ не достигнет ограничения.
Следующих людей наделяем характеристиками $m_3,\cdots,m_{p+2}$, пока лимит на $m_3$ не исчерпается.
И так далее.

[main.c]

Да, это был 1 из моих вариантов, но вот случай, когда он не работает: есть 3 характеристики, 3 ограничения по 100, $p = 2$, заполняем до упора 1 и 2, в итоге имеем, что характеристики 1 и 2 заполнены и у нас 100 человек. Больше мы получить людей не сможем. Но максимальное количество не 100, а 150. Достигается это так, 50 человек заполняют 1 и 2 характеристику, затем 50 заполняют 2 и 3, и затем 50 заполняют 1 и 3, в итоге 150 человек.

[svv]

Да, Вы правы! Не работает.

[slavav]

svv в сообщении #1130357 писал(а):

Да, Вы правы! Не работает.

Зато работает модификация вашего алгоритма: отсортируем $m_i$ по убыванию. Выберем первые $p$ членов. Соответствующие номера $m_i$ уменьшим на единицу, нули выбросим и снова отсортируем $m_i$ по убыванию. Будем повторять пока в списке хотя бы $p$ членов.

[main.c]

slavav, да, спасибо, я как раз к этому и пришел, и даже этот алгоритм можно модифицировать, не прибавлять по единице, а прибавлять прям кусками. Просто это некий итеративный алгоритм, и как вариант Б мне этого хватит для текущей практической задачи. Но спортивный интерес заставляет меня поискать решение этой задачи одной формулой. Но видимо её не существует. Или все-таки можно что-то придумать?

[slavav]

Есть простая формула, если все $m_i$ варьируются не более чем на единицу. Можно показать, что приведённый алгоритм сохраняет это свойство как инвариант. В конце мы получим вектор из менее чем $p$ единиц. Тогда $K = \left\lfloor\frac{\Sigma m_i}{p}\right\rfloor$.

[main.c]

Есть более продвинутый алгоритм, но я не знаю, как его доказать.
1. Сортируем в обратном порядке
2. Считаем сумму всех элементов, назовем ее $S$
3. $i = 1$
3. Если $p = 1$ или $i > n$ или $m_i \leq \frac{S-m_i}{p - 1}$, переходим к шагу 8
4. $S = S - m_i$
5. $p = p - 1$
6. $i = i + 1$
7. Переходим к шагу 3
8. Ответ равен: $[\frac{S}{p}]$

Есть ли идеи как это доказать?