Гнилі Мотузки

Припустимо, у нас є $n$ мотузок однакової довжини, і ми хочемо використати їх для підйому важкого об'єкта. Кожна мотузка має свою розривну вагу $t$, тобто якщо ми намагаємося підняти об'єкт, важчий за $t$ за допомогою цієї мотузки, вона порветься. Проте, ми можемо прикріпити кілька мотузок до важкого об'єкта (паралельно) і підняти його всіма прикріпленими мотузками. Коли використовуються $k$ мотузок для підйому важкого об'єкта з вагою $w$, ми припускаємо, що кожна з $k$ мотузок, незалежно від її розривної ваги, відповідає за підйом ваги $w/k$. Однак, якщо w/k > t для якоїсь мотузки з розривною вагою $t$, ця мотузка порветься.

Наприклад, три мотузки з розривними вагами $1$, $10$ і $15$, коли всі три прикріплені до об'єкта, не можуть підняти об'єкт з вагою більше $3$, якщо не порветься найслабша. Але друга мотузка може підняти сама по собі об'єкт з вагою не більше $10$.

З огляду на розривні ваги $n$ мотузок, ваше завдання - знайти вагу найважчого об'єкта, який можна підняти, прикріпивши підмножину даних мотузок без розриву жодної з них.