2.2.6. Разбиение выпуклого n-угольника

Дан выпуклый N-угольник, заданный координатами своих вершин в порядке обхода. Он разрезается N-2 диагоналями на треугольники. Стоимость разрезания определяется суммой длин всех использованных диагоналей. Найти разрез минимальной стоимости.

Идея решения разбирается с использованием следующего рисунка.

Обозначим через S[k,l] стоимость разрезания многоугольника A[k,l] диагоналями на треугольники. При l=k+1 или k+2 S[k,l]=0, следовательно, l>k+2. Вершина с номером 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 имеет вес w_i и стоимость v_i (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через k_i, тогда требуется максимизировать v₁*k₁+v₂*k₂+...+v_n*k_n при ограничениях w₁*k₁+w₂*k₂+...+w_n*k_n£W, где k_i - целые (0£k_i£[W/w_i]), квадратные скобки означают целую часть числа.

Пусть вес рюкзака должен быть равен W. Формализуем задачу следующим образом.

• Шаг i ставится в соответствие типу предмета i=1,2,...,n.

• Состояние y_i на шаге i выражает суммарный вес предметов, решение о загрузке которых принято на шагах 0,1,...,i. При этом y_n=W, y_i=0,1,...,W при i=1,2,...,n-1.

• Варианты решения k_i на шаге i описываются количеством предметов типа i, 0£k_i£ëW/w_iû.

  Рассмотрим пример. 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; end;

Var A:array[1..MaxN,0..MaxK] of word;

P:array[1..MaxN] of Thing;

Old,NewA:array[0..MaxK] of longint;

N,W:integer;

...

procedure Solve;

var k,i,j:integer;

begin

fillchar(Old,sizeof(Old),0);

for k:=1 to N do begin{цикл по шагам}

fillchar(NewA,sizeof(NewA),0);

for i:=0 to W do {цикл по состояниям шага}

for j:=0 to i div P[k].W do {цикл по вариантам решения - количеству предметов каждого вида}

if j*P[k].V+Old[i-j*P[k].W]>=NewA[i] then begin

NewA[i]:=j*P[k].V+Old[i-j*P[k].W];

A[k,i]:=j;{здесь j количество предметов?}

end;

Old:=NewA;

end;

end;

Вывод наилучшего решения.

procedure OutWay(k,l:integer);

begin

if k=0 then exit

else begin

OutWay(k-1,l-A[k,l]*P[k].V);{а здесь вес}

Write(A[k,l],’ ‘);

end;

end;

Первый вызов - OutWay(N,W). Эту схему реализации принято называть «прямой прогонкой». Ее можно изменить. Пусть пункт два формализации задачи звучит следующим образом. Состояние y_i на шаге i выражает суммарный вес предметов, решение о загрузке которых принято на шагах i, i+1, ..., N при этом y₁=W y_i=0,1,...,W при i=2,3, ...,N. В этой формулировке схему реализации называют «обратной прогонкой».