Вариант с рюкзаком?

Question

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

Итак, я иду по магазинам и у меня есть х денег, мой грузовик может набрать вес до y, а у каждого предмета есть бонусный кредит вес и цена.Результат должен дать максимальный бонус, который можно получить таким образом, чтобы общий вес выбранных предметов не превышал грузоподъемность грузовика и деньги, которые я должен потратить!Вы знаете название алгоритма?Как мне поступить?Я должен сделать это в C!

Спасибо !!

Answer 1

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

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

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

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

Жадный алгоритм может занять всего 1577,25 доллара.
Оптимальное значение3 книжных шкафа и стол = 1600 долларов.

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

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

Answer 2

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

Answer 3

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

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

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