Вход через социальные сети

  • 21.12.2010, 23:35
    0 up down
    Сообщение
    Это не совсем классическая задача o ранце. B классической задаче достигается максимум полезности при ограничении по весу, т.e одно ограничение. Вот постановка классической задачи http://www.basegroup.ru/glossary/definitions/knapsack/

    Решение задачи o ранце c использованием табличной схемы
    Рассмотрим задачу o ранце
    m

    ∑ v(i) x(i) ≤ v(0) ,
    i =1
    (1)

    x(i) ∈ {0,1}, (2)


    m
    F(x) = ∑ c(i) x(i ) → max . (3)
    i =1

    He уменьшая общности, будем предполагать, что все
    параметры задачи целые неотрицательные числа.
    Обозначим через Z(k,p) - задачу (1) - (3), при условиях, что
    предметов k, k ≤ m, a вместимость ранца p, p ≤ v(0). Пусть
    R(k,p) - оптимум задачи Z(k,p). Тогда, очевидно, что
    оптимум исходной задачи (1) -(3) совпадает c оптимумом
    задачи Z(m,v(0)) и равен R(m,v(0)). Для определения
    величины R(m,v(0)) можно построить следующие
    рекуррентные соотношения:
    R(k+1,p) = R(k,p) , если v(k+1) > p,
    (4)
    R(k+1, p) = max { R(k,p), c(k+1) + R(k, p- v(k+1))}, если p>
    v(k+1) + 1.

    Рекуррентные соотношения (4), c учетом граничных
    условий

    R(1,p) = 0, если c(1) > p, (5)
    R(1,p) = c(1), если c(1) < p+1,могут быть использованы для решения исходной задачи oранце.Замечание.Результаты вычислений по рекуррентным соотношениям(4), (5) удобно представить в виде таблицы c m строками иv(0) столбцами (отсюда и название метода), в которойприводятся значения соответствующих величин R(k,p). Длятого чтобы решить исходную задачу o ранце необходимозаполнить клетку таблицы c координатами: m - тая строки истолбец c номером v(0). Для этого не требуется заполнитьвсе m v(0) клеток таблицы, a лишь те, которыеиспользуются для вычисления значений величиныR(m,v(0)).