целую часть числа. Пусть


целую часть числа. Пусть вес рюкзака должен быть равен 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;
Индекс
Элементарные функции    Линейные уравнения    Нелинейные уравнения    Случайные числа


Hosted by uCoz