Вершина с номером
Вершина с номером i, i изменяется от k+1 до l-1, определяет какое-то разрезание многоугольника A[k,l]. Cтоимость разрезания определим как:
S[k,l]=min{длина диагонали <k,i>+длина диагонали <i,l>+S[k,i]+S[i,l]}. При этом следует учитывать, что при i=k+1 диагональ <k,i> является стороной многоугольника и ее длина считается равной нулю.
Пример(N=6).
2.2.7. Задача о рюкзаке (динамическая схема)
Рассмотрим задачу из пункта 1.1.6. Напомним ее формулировку. В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака не превышает W. Каждый предмет типа i имеет вес wi и стоимость vi (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через ki, тогда требуется максимизировать v1*k1+v2*k2+...+vn*kn при ограничениях w1*k1+w2*k2+...+wn*kn?W, где ki - целые (0?ki?[W/wi]), квадратные скобки означают
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
