Учитывая совокупность потребителей, конкурирующих за ограниченный ресурс, выделите этот ресурс, чтобы максимизировать его применимость

Question

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

У меня есть несколько друзей, чьи дни рождения приближаются к датам (d1..dn), и мне удалось придумать несколько подарков, которые я хотел бы купить их по цене (c1..cn ). К сожалению, у меня есть только фиксированная сумма денег (м), которую я могу сэкономить в день на покупку этих подарков. Вопрос, который я хотел бы задать:

Каково идеальное распределение сбережений на подарок (mi, где сумма mi от 1..n == m), чтобы минимизировать общее отклонение между днями рождения моих друзей и датой, в которую я буду иметь накопил достаточно денег, чтобы купить этот подарок.

То, что я ищу, - это либо решение этой проблемы, либо отображение решенной проблемы, которое я могу использовать для детерминированного ответа на этот вопрос. Спасибо за размышление, и дайте мне знать, если я могу дать какие-либо дополнительные разъяснения!

Answer 1

Я думаю, что вы указали форму проблемы с рюкзаком с некоторыми дополнительными сложностями - проблема с рюкзаком - NP-Complete (с. 247, Гэри и Джонсон). Основная проблема рюкзака заключается в том, что у вас есть несколько объектов, каждый из которых имеет объем и значение - вы хотите заполнить рюкзак фиксированного объема объектами, чтобы максимизировать значение без превышения вместимости рюкзака.

Учитывая, что у вас есть этапы (дни) и ресурсы (деньги), а ресурсы меняются день ото дня, пока вы решаете, какие покупки делать, я бы привел к использованию метода динамического программирования, а не модели прямой оптимизации.

Не могли бы вы уточнить в комментариях "минимизация отклонений"? Я не уверен, что понимаю эту часть.

Кстати, mathoverflow.com, вероятно, не поможет в этом. Если вы посмотрите на вопросы алгоритма, 50 по стеку потока и 50 по mathoverflow, вы обнаружите, что вопросы (и ответы) по стеку потока имеют гораздо больше общего с проблемой, которую вы рассматриваете. Существует новый сайт, который называется OR Exchange, но трафика там пока немного.