Маленький вопрос о задаче о рюкзаке

[damir_777]

Предположим задан вес рюкзака 5000 единиц. Каждый предмет можно загружать неограниченное кол-во раз.
Заданы определенный предметы с их ценами. Допустим имеется два алгоритма. Оба нашли одинаковую максимальную стоимость, но первый выдал что результирующий вес рюкзака при этом будет 5000, а второй что 4500. Хотел спросить, существенно ли чтобы при этом вес рюкзака должен быть как можно меньше, или главное максимизация стоимости? Т.е например при решении задачи с помощью динамического программирования ищется только макс. стоимость , но метод как бы не заботится чтобы и вес был как можно меньше. Т.е получается что меньший вес просто предподчительней, но не главное?

[Dmitriy40]

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

[damir_777]

Получается если нужно найти максимальную стоимость рюкзака и при этом получить как можно меньший его вес, то это задача становится двухкритериальной? А есть ли методы которые одновременно решают эти две задачи? Ну методом динамического программирования ето уж точно не решить)

[Dmitriy40]

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

[provincialka]

Пока ждем специалистов,выскажу соображения здравого смысла.
Есть еще один способ: для всех критериев, кроме одного, вводятся границы допустимых значений, а по одному оптимизируют. Ну, и еще можно оптимизировать последовательно: вдруг с одной ценой есть несколько заполнений рюкзака? Тогда можно выбрать из них наибольший по массе. Или наоборот, среди самых "тяжелых" найти самый дорогой.

[Dmitriy40]

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

[grizzly]

damir_777
Вы посмотрите литературу по задаче о рюкзаке. Это большой класс задач, которые изучаются при самых различных постановках. Конечно, Dmitriy40 прав -- решение о том, какие критерии оптимизации нас интересуют, принимается на этапе постановки задачи. Легко представить ситуацию, когда алгоритм, выдающий 5000 будет лучше, чем алгоритм выдающий 4500; и ещё легче -- наоборот.

Кстати, поделюсь (английской) ссылкой на лучшее, что мне попадалось по теории для этой задачи. Может, кому пригодится.

(Оффтоп)

Если тема не повернёт в математическую сторону, я попрошу модераторов перенести её в CS -- там смогут её увидеть специалисты.

[damir_777]

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

-- 28.04.2016, 15:33 --

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

[ET]

damir_777 в сообщении #1118706 писал(а):

Получается если нужно найти максимальную стоимость рюкзака и при этом получить как можно меньший его вес, то это задача становится двухкритериальной? А есть ли методы которые одновременно решают эти две задачи? Ну методом динамического программирования ето уж точно не решить)

А в чем вообще проблема?
Кажется при решении задачи о рюкзаке строятся решения для всех рюкзаков объема меньших, чем заданный
Там же строится функция (таблица) от 2х аргументов (k,m): 1. используя предметы от 1..к 2. для рюкзака объемом m
И к моменту расчета нужного значения. все предыдущие значения уже расчитаны
А значит учесть 2й критерий очень прсто