Алгоритм Дейкстры, итерационный алгоритм
Добавлено: 22 май 2009, 17:45
Всем привет, помогите пожалуйста кто чем может. Есть задание: пакет, содержащий n программ выполняется однопрограммной ЭВМ. Известна длительность прохождения каждой программы tk и директивный срок Dk, к которому желательно завершить выполнение k-й программы. Функция штрафа jk(x)=max(x-Dk,0) Определить такой порядок выполнения программ, при котором суммарный штраф будет минимален. -фактическое время завершения работы k-й программы.
Известно что для получения следующей перестановки может быть использован итерационный алгоритм:
Переменные:
c : вектор;
i,j : целое;
Начало:
i:=n-1;
Пока (c>=c[i+1]) i:=i-1;
j:=n;
Пока (c[j]<=c) j:=j-1;
c:переставить(i,j);
i:=i+1; j:=n;
Пока (i<j)
н.ц.
c:переставить(i,j);
i:=i+1;
j:=j-1;
к.ц.
Конец.
Не знаю как реализовать перестановку, для одной перестановки определил штраф так:
Эта часть проги работает, признателен за любую помощь
Известно что для получения следующей перестановки может быть использован итерационный алгоритм:
Переменные:
c : вектор;
i,j : целое;
Начало:
i:=n-1;
Пока (c>=c[i+1]) i:=i-1;
j:=n;
Пока (c[j]<=c) j:=j-1;
c:переставить(i,j);
i:=i+1; j:=n;
Пока (i<j)
н.ц.
c:переставить(i,j);
i:=i+1;
j:=j-1;
к.ц.
Конец.
Не знаю как реализовать перестановку, для одной перестановки определил штраф так:
Код: Выделить всё
#include <iostream>
using namespace std;
void main()
int t[5];
int d[5];
float x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x;
for(int q=0;q<5;q++)
{
cout<<" Tk"<<q+1<<": ";
cin>>t[q];
}
for(int z=0;z<5;z++)
{
cout<<" Dk "<<z+1<<": ";
cin>>d[z];
}
if (x1>0){y1=x1;} else y1=0;
x2=t[1]+t[0]-d[1];
if (x2>0){y2=x2;} else y2=0;
x3=t[2]+t[1]+t[0]-d[2];
if (x3>0){y3=x3;} else y3=0;
x4=t[3]+t[2]+t[1]+t[0]-d[3];
if (x4>0){y4=x4;} else y4=0;
x5=t[4]+t[3]+t[2]+t[1]+t[0]-d[4];
if (x5>0){y5=x5;} else y5=0;
x=y1+y2+y3+y4+y5;
cout<<"sumarnuj shtraf:"<<x;
}