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

Question

[Agiot]

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

Как решить задачу о рюкзаке, если рюкзак ограничен не только грузоподъемностью, но и количеством предметов, которые можно в него положить (причем количество предметов должно быть равно этому ограничению, не больше и не меньше)?

Comments

[sim3x]

Загляните в вики

Answer 1

[Alexej Simakov]

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

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

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

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

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

Comments

[Agiot]

Да, Вы правильно поняли. Решение "в лоб" я использую, но, решил поискать более оптимальное решение, например, методом динамического программирования, т.к. решение "в лоб" не всегда устраивает по временнЫм показателям.

[Alexej Simakov]

Agiot об вычислительной оптимизации в вопросе ничего не было сказано :)