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

Question

Мне дан список n продуктов с соответствующей прибылью и стоимостью за единицу. Цель состоит в том, чтобы максимизировать прибыль при сохранении общей стоимости ниже определенного порога. Для каждого продукта создаются либо один, либо ноль.

Теперь предположим, что у нас есть три продукта. Предположим, что эти метки обозначены следующими 1,2 и 3. Тогда все возможные комбинации производств могут быть заданы как двоичные числа 111,110,101,011,100,010,001 и 000, где 1 в i-м положении обозначает производство одного из продуктов i и аналогично для нуля. Тогда мы могли бы легко проверить, какая из этих комбинаций имеет себестоимость под порогом и имеет максимальную прибыль. Тогда этот алгоритм был бы порядка O (2^n), так как для n произведений мы должны проверить двоичные числа 2^n. Вероятно, мы можем сделать это немного быстрее, узнав, что если 100 выше порога, нам не нужно проверять 110 и 111 и некоторые подобные вещи, но из-за этого порядок не изменится. Как я могу сделать более разумный алгоритм, возможно, это имеет более сложную временную сложность. N может достигать 100, в этом случае проверка 2^100 номеров невозможна. Заранее спасибо

Answer 1

Если ваши затраты являются целыми, которые не слишком велики, вы можете использовать решение динамического программирования для проблемы с рюкзаком, указанное в ссылке, упомянутой в комментарии Дэвида Эйзенстата. Если ваши затраты являются либо большими целыми числами, либо дробными, то лучше всего использовать один из существующих решателей ранца, например, свести к целочисленной проблеме линейного программирования, а затем сделать что-то вроде ветви и границы для решения. Во всяком случае, ваша проблема - проблема с рюкзаком, с единственной незначительной модификацией, которую вам не нужно полностью заполнять рюкзаком, вы можете заполнить ее частично, пока вы ее не переполняете. Однако этот вариант также изучается вместе с оригинальной формулировкой, и для этого существуют решатели. Также легко изменить решение динамического программирования, чтобы справиться с этим, дайте мне знать, если неясно, как и я буду обновлять свой ответ с объяснением.