Непрерывный и дискретный рюкзак

Есть $n$ слитков золота. Слиток $i$ весит $m_i$ и стоит $c_i$. Рюкзак выдерживает $M$. Нужно унести как можно больше по стоимости.

Дальше одно слово меняет всё.

Если резать можно

Слитки однородные, отрезать разрешается любую долю. Формально ищем $p_i \in [0, 1]$:

$$\sum p_i m_i \le M, \qquad \sum p_i c_i \to \max$$

Задача решается жадно и очевидно: сортируем по удельной стоимости $c_i / m_i$ и набираем сверху, пока рюкзак не заполнится. Последний слиток режем ровно на остаток.

sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
    return a.cost * b.mass > b.cost * a.mass;   // a.cost/a.mass > b.cost/b.mass
});

double total = 0, left = capacity;
for (const Item& item : items) {
    if (left <= 0) break;
    double take = min(item.mass, left);
    total += item.cost * take / item.mass;
    left -= take;
}

Сравнение через умножение крест-накрест, а не делением: так нет ни деления на ноль, ни потери точности. Приём общий — сравнивая дроби, умножайте.

Сложность — $O(n \log n)$, целиком на сортировке.

Почему это верно: если в оптимальном ответе взят грамм менее выгодного слитка, а какой-то грамм более выгодного остался, обмен одного на другой не уменьшает стоимость. Значит, существует оптимальный ответ, где слитки берутся по убыванию удельной стоимости, — а это ровно наш.

Если резать нельзя

Теперь $p_i$ равно строго нулю или единице. Задача выглядит проще — вариантов меньше. На самом деле она принципиально сложнее: жадностью не решается никак.

Контрпример к сортировке по удельной стоимости. Вместимость $10$:

слиток	масса	стоимость	удельная
A	8	16	2.0
B	7	13.3	1.9
C	3	3	1.0

Жадность берёт A (осталось 2), больше ничего не влезает — итого 16. Оптимум — B и C: $13.3 + 3 = 16.3$.

Контрпример к сортировке по абсолютной стоимости строится ещё проще: один дорогой тяжёлый слиток против россыпи мелких, суммарно более ценных.

Общая причина: локальный выбор «взять самый выгодный» портит остаток вместимости. В непрерывном варианте остаток всегда можно доесть долей, поэтому вреда нет. В дискретном остаток может пропасть впустую.

Что делать с дискретным

Динамическое программирование. Состояние — «максимальная стоимость при вместимости $w$, если рассмотрены первые $i$ предметов»:

vector<long long> best(capacity + 1, 0);
for (const Item& item : items)
    for (int w = capacity; w >= item.mass; w--)
        best[w] = max(best[w], best[w - item.mass] + item.cost);

Внутренний цикл идёт по убыванию — иначе один предмет возьмётся несколько раз. Сложность $O(n \cdot M)$: это не полином от размера входа (масса задаётся числом, а не количеством цифр), но при $M$ до $10^5$ работает прекрасно.

Когда вместимость огромная, а предметов мало ($n \le 40$), применяют встречу посередине: перебирают все подмножества каждой половины за $2^{20}$ и склеивают их бинарным поиском.

Как это распознать в условии

Разница между «можно резать» и «нельзя» — это разница между $O(n \log n)$ и динамикой. В условии она прячется в одном слове, и его легко пропустить.

Признаки непрерывного варианта: «в любых пропорциях», «жидкость», «песок», «можно взять часть», ответ — вещественное число.

Признаки дискретного: «предмет либо берём целиком, либо не берём», ответ — целое число, ограничения вида $n \le 100$, $M \le 10^5$ (перемножьте — получите как раз размер таблицы динамики).

Ограничения часто и есть подсказка. Если $n \le 10^5$, динамика не влезет, и задача точно жадная. Если $n \le 100$, а вместимость до $10^4$ — вас ждут именно с динамикой.

Родственные задачи, где жадность работает

Не всякая задача про «набрать в ограниченный объём» дискретна и трудна:

• все стоимости равны («унести как можно больше предметов»): сортируем по массе и берём лёгкие. Жадность верна;
• все массы равны («выбрать $k$ предметов»): сортируем по стоимости. Жадность верна;
• предметов каждого типа бесконечно много, резать нельзя: всё равно динамика, но состояние проще;
• нужно ровно заполнить рюкзак: это подзадача о сумме подмножества, тоже динамика.

Правило, которое из этого следует: жадность выживает там, где предметы сравнимы по одному признаку. Как только их два — масса и стоимость независимо, — жадность почти наверняка ломается, и стоит проверить её стрессом прежде, чем писать решение.