Planowanie prac
Kod był wyświetlany 1241 razy.
    /*
  Name: Planowanie prac
  Copyright: GPL GNU
   Date: 01-04-10 17:26
  Description:
 Przypuśćmy, że dysponujemy maszyną i dany jest zbiór n prac do wykonania na tej maszynie. Dla każdej pracy znany jest czas jej wykonania t, zysk p oraz nieprzekraczalny termin ukończenia tej pracy. Na maszynie nie można wykonywać jednocześnie więcej niż jednej pracy, a wykonywanie pracy nie może być przerywane i musi trwać t jednostek czasu. Jeśli praca zostaje ukończona terminowo, nasz zysk wynosi p. Jeśli nie zostaje ukończona terminowo, zysk jest zerowy. Ułóż algorytm, który zaplanuje wykonanie prac na maszynie w sposób maksymalizujący zysk. 
*/

#include <iostream>
#include <conio.h>
using namespace std;
int *poprz;
void Wyswietl(int nr)
{
	if(poprz[nr]>-1)
		Wyswietl(poprz[nr]);
	cout<<nr+1<<" ";
}
int main()
{
	int n;
	cout<<"Ile prac: ";
	cin>>n;
	int *czas=new int[n],*zysk=new int[n],*termin=new int[n],*tymczZysk=new int[n],*tymczCzas=new int[n];
	poprz=new int[n];
	int a;
	cout<<"Podaj kolejno zyski z wykonanych prac: ";
	for(int i=0;i<n;i++)
	{
		cin>>a;
		zysk[i]=a;
	}
	cout<<"Podaj kolejno czasy wykonania prac: ";
	for(int i=0;i<n;i++)
	{
		cin>>a;
		czas[i]=a;
	}
	cout<<"Podaj kolejno terminy wykonania prac: ";
	for(int i=0;i<n;i++)
	{
		cin>>a;
		termin[i]=a;
	}
	for(int i=0;i<n;i++)
	{
		if(czas[i]<=termin[i])
		{
			tymczZysk[i]=zysk[i];
			tymczCzas[i]=czas[i];
		}
		else
			tymczZysk[i]=tymczCzas[i]=0;
		poprz[i]=-1;
		for(int j=0;j<i;j++)
		{
			if(tymczCzas[j]+czas[i]<=termin[i]&&tymczZysk[j]+zysk[i]>tymczZysk[i])
			{
				tymczZysk[i]=tymczZysk[j]+zysk[i];
				tymczCzas[i]=tymczCzas[j]+czas[i];
				poprz[i]=j;
			}
		}
	}
	int nr,max=0;
	for(int i=0;i<n;i++)
		if(tymczZysk[i]>max)
		{
			max=tymczZysk[i];
			nr=i;
		}
		cout<<"Kolejnosc optymalnych prac to: ";
	Wyswietl(nr);
	getch();
	return 0;
}    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT