Frenzy Nicky_NВсем доброго дня!
Необходимо решить классическую задачу о рюкзаке(из множества предметов, каждый из которых имеет свою стоимость и ценность, требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную ценность при одновременном соблюдении ограничения на суммарную стоимость):
(∑pjxj) –> max,
∑wjxj ≤ c,
xj = {0;1}, j = 1..n, где pj - ценность вещи j, wj - стоимость вещи j.
примеры с недискретным х нигде не приводятся, потому что в этом случае задача становится намного более тривиальной, если х неограничены, то выбираем х с наибольшим соотношением pj/wj - и набираем полный рюкзак самых выгодных иксов (т.е. максимум сколько влезает в с). если х ограничены (как у вас единицей в вашем условии), то сортируем иксы по убыванию выгодности (выгодность pj/wj), и берем максимум самых выгодных иксов, затем максимум вторых по выгодности и так далее пока не заполним рюкзак (т.е. пока не получим общую цену иксов с).
а все приведенные ваши алгоритмы как раз придумывались для случая с дискретными х, т.к. задача намного сложнее как раз с дискретными
вы говорите о классическом жадном алгоритме, для дискретной задачи он не дает оптимального решения(контрпримеры -
стр 456-457 и
тут ).
