Рюкзак вариации?

Question

Я искал этот тип алгоритма и много красных вещей, но я не мог найти именно то, что я ищу.

Итак, я иду по магазинам, и у меня есть x деньги, мой грузовик может принять вес, и каждый товар имеет бонус-кредит веса и цены. Результат должен предоставить максимальный бонусный кредит, который можно получить таким образом, чтобы общий вес выбранных предметов не превышал емкость грузовика и деньги, которые я должен потратить!

Я мог бы помочь вам здесь, ребята, знаете ли вы название алгоритма? Как я могу продолжить? Я должен сделать это в C!

Спасибо!

Answer 1

Что вы пробовали?

Эти проблемы обычно относятся к категории оптимизации или ограничения удовлетворения.

Попробуйте написать функциональное выражение для своей проблемы и посмотреть, можете ли вы решить его с помощью простых методов исчисления или симплекс.

Answer 2

Я знаю два варианта проблемы с рюкзаком. Версия 0-1 не может содержать дробные веса (взять ее или оставить), например, я не могу взять половину второго лучшего выбора. Другая версия - противоположная, допускаются дробные элементы. Эта небольшая разница чрезвычайно важна и работает в пользу дробной версии.

Дробная версия может быть решена с помощью жадного алгоритма. Вы можете просто взять столько, сколько сможете, с помощью самой ЦЕННОЙ «цены за единицу». Повторяйте, пока ваш грузовик не будет заполнен.

Версия 0-1 немного сложнее, так как она не может быть решена с помощью простого жадного алгоритма. Например, ваш грузовик может перевозить 800 фунтов. Мы можем выбрать из

1. 1 табл весом 500 фунтов со значением $ 1000 (цена единицы $ 2/фунт)
2. 1 слесарно: вес - 701lb: значение - $ 1577,25: Блок $ 2.25/фунт
3. 3 Книжные шкафы : вес - 100 фунтов: стоимость - 200 долл. США: единица 2 долл. США/фунт

Жадный алгоритм займет скамейку на общую сумму 1577,25 долл. США.
Оптимальное значение - 3 книжных шкафа, а таблица = 1600 долларов.

Если бы это была версия с дробным рюкзаком, она бы просто взяла скамейку и 99 фунтов стола/книжного шкафа на общую сумму 1775,25 долларов.

В случае 0-1 нам нужно использовать что-то вроде динамического программирования для изучения всех решений.

Answer 3

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