Как решить задачу о рюкзаке 0-1 (ее разновидность)?
Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. Также имеется рюкзак определённой вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарный вес. Все предметы - в единственном экземпляре.
Как решить задачу о рюкзаке, если рюкзак ограничен не только грузоподъемностью, но и количеством предметов, которые можно в него положить (причем количество предметов должно быть равно этому ограничению, не больше и не меньше)?
Я так понимаю, что особенность Вашей задачи в том, что количество предметов должно быть именно строго равно ограничению? В стандартных задачах ограничения по количеству выбраных предметов нет.
Перефразирую задачу:
Допустим, у вас всего в наличии N предметов, a рюкзак должен быть укомплектован К предметами, причем К<=N. Нужно выбрать такую комплектацию, чтобы общий вес не превышал максимально допустимый и общая ценность предметов была наиболее высокой.
Предлагаю Вам решение "в лоб":
Создайте список всех сочетаний K над N (для комбинаторных рассчетов есть специальные библиотеки для большинства языков программирования). Для каждого сочетания рассчитайте его вес и уберите те сочетания которые превышают ограничение по весу. Оставшиееся сочетания отосортируйте по убыванию ценности и возьмите самые верхние.
Да, Вы правильно поняли. Решение "в лоб" я использую, но, решил поискать более оптимальное решение, например, методом динамического программирования, т.к. решение "в лоб" не всегда устраивает по временнЫм показателям.
Средний
