Экономико-математические методы и модели

лекция 10
23.04.2020

масса), и имеются предметы (n штук), причем каждый предмет характеризуется

массой w и ценностью P. w = {w1, w2, …, wn} p={p1, p2, …, pn}
Требуется собрать рюкзак с максимальной ценностью и минимальным возможным весом, не превышающим Wmax. 1 способ: перебор (простой) 2 способ: метод ветвей и границ, который заключается в умном переборе. Могут быть случаи, когда перебираются все возможные варианты. 3 способ: использование «жадного» алгоритма (берется каждый текущий момент («лучший» элемент), ориентированный на их относительной точности). Решение будет получено достаточно быстро, но не факт, что оно будет оптимальным.

n предметов, характеризующихся целочисленными показателями весов wi и ценностей pi.

Требуется построить вектор бинарных величин В = {b1, b2, …, bn} (0 – не положили в рюкзак, 1– положили) так, чтобы при выполнении ограничения b1w + b2w2 + … + bnwn = ( )=

результата, достигнутого на предыдущих этапах, то есть, каждый раз, решая

задачу о необходимости загрузить рассматриваемый предмет в рюкзак, пытаемся решить задачу, анализируя те результаты, которые были достигнуты ранее, то есть до того как мы начали рассматривать текущий k-й предмет, а именно, основываясь на том как был упакован рюкзак предметами с номерами 1,2, …,k-1, причем, необходимо еще учитывать минимальность веса, то есть рассматривать возможность веса рюкзака от 0 до w.

в
матрице А(k,s).
Все величины целочисленные.
k – номер текущего

предмета, который может быть положен в рюкзак;
s- текущий рассматриваемый вес рюкзака.

Учитывая исходные данные, матрица будет (5х15). Элемент матрицы А будет иметь смысл максимальной возможной стоимости при весе меньшем или равном s в случае возможности разместить в рюкзаке k-первых предметов. Для удобства расчетов будем рассматривать нулевой столбец и нулевую строку, которые полностью заполнены нулями.
A(0,i) = 0; A(j,0) = 0; для любых i=0,15; j=0,5

A[k-1,s], A[k-1, s – w[k]] + p[k] )
Будем заполнять матрицу

по строкам, то есть каждая строка соответствует анализу k-го предмета.
A[4,10] = max( A[3,10], A[3,8] + 3) = max (8,11)