целую часть числа. Пусть
целую часть числа.
Пусть вес рюкзака должен быть равен W. Формализуем задачу следующим образом.
• Шаг i ставится в соответствие типу предмета i=1,2,...,n.
• Состояние yi на шаге i выражает суммарный вес предметов, решение о загрузке которых принято на шагах 0,1,...,i. При этом yn=W, yi=0,1,...,W при i=1,2,...,n-1.
• Варианты решения ki на шаге i описываются количеством предметов типа i, 0?ki??W/wi?.
Рассмотрим пример. W=6, и дано четыре предмета
i wi vi
1 2 50
2 3 90
3 1 30
4 4 140
Схема работы для данного примера приведена на рисунке. В кружочках выделены только достижимые состояния (суммарные веса для каждого шага в соответствии с приведенной выше формализацией) на каждом шаге. В круглых скобках указаны стоимости соответствующих выборов, в квадратных скобках - максимальная стоимость данного заполнения рюкзака. «Жирными» линиями выделен способ наилучшей загрузки рюкзака.
Текст решения.
Const MaxN=???;
MaxK=???;
Type Thing=Record W,V:Word;
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
