@Agiot

Как решить задачу о рюкзаке 0-1 (ее разновидность)?

Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. Также имеется рюкзак определённой вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарный вес. Все предметы - в единственном экземпляре.

Как решить задачу о рюкзаке, если рюкзак ограничен не только грузоподъемностью, но и количеством предметов, которые можно в него положить (причем количество предметов должно быть равно этому ограничению, не больше и не меньше)?
  • Вопрос задан
  • 673 просмотра
Решения вопроса 1
lxsmkv
@lxsmkv
Test automation engineer
Я так понимаю, что особенность Вашей задачи в том, что количество предметов должно быть именно строго равно ограничению? В стандартных задачах ограничения по количеству выбраных предметов нет.

Перефразирую задачу:

Допустим, у вас всего в наличии N предметов, a рюкзак должен быть укомплектован К предметами, причем К<=N. Нужно выбрать такую комплектацию, чтобы общий вес не превышал максимально допустимый и общая ценность предметов была наиболее высокой.


Предлагаю Вам решение "в лоб":

Создайте список всех сочетаний K над N (для комбинаторных рассчетов есть специальные библиотеки для большинства языков программирования). Для каждого сочетания рассчитайте его вес и уберите те сочетания которые превышают ограничение по весу. Оставшиееся сочетания отосортируйте по убыванию ценности и возьмите самые верхние.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы