Задача о ранце (рюкзаке) — одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Содержание |
Задача о ранце в случае, когда вес каждого предмета представляет собой целое число, может быть решена с помощью динамического программирования. Но важно отметить, что задача о ранце является NP-задачей (псевдо-полиномиальна).
По данному набору из n предметов стоимостями и весами найти поднабор (с учетом того, что можно брать один предмет несколько раз) такой, что его стоимость будет максимальна среди всех поднаборов веса не более W.
Обозначим через максимальную стоимость, которую мы можем набрать при весе не более w. Получаем следующее рекуррентное соотношение:
Использовать рекурсию напрямую нельзя, так как появляется большое число перекрывающихся задач и время выполнения может стать экспоненциальным. При использовании динамического программирования(запоминания) мы получаем сложность O(n * W) — псевдополиномиальный алгоритм.
Задача о ранце табличный метод, задача о ранце решение в excel, задача о ранце применение, задача о ранце методом ветвей и границ онлайн.
Категория:Тренеры ФК «Кру Александра», Категория:Статьи проекта Древний Египет по уровню, Категория:Игроки ФК «Фаукнер Блюс», Категория:Шаблоны:Саскачеван.
