[C++] Obiekty - Problem Optymalizacyjny

#include <iostream>
#include <cstring>
#include <time.h>
#include <windows.h>
#include <conio.h>
using namespace std;



int KontenerCiezar[ 100 ];
int KontenerWartosc[ 100 ];
int WartosciWazone[ 100 ];
int WartosciWazoneINDEX[ 100 ];

class Wynik;
class Element;
class Kombinacja;
class ZbiorKombinacji;

void kolor( int kk );
void nadpis( const int xxxvv, const int yyyvv );
int max( int a, int b );
void Heapify( int heap_size, int i );
void buduj_kopiec( int HeapSize );
INT64 HS( int size );
void generuj_zbior( int nKONTENEROW, int WartoscMIN, int WartoscMAX, int CiezarMIN, int CiezarMAX );
void BestDynamo( int Ladownosc, int nKONTENEROW );
void BestBruteForce( int Ladownosc, int nKONTENEROW );
void BestAlgZachlanny( int Ladownosc, int nKONTENEROW );
void WykonajWartosciWazone( int nKONTENEROW );
int zastap_element( int * zastepowany, int * tymzastapiony );
void podmien_elementy( int * x, int * y );
void przeprowadz_proby( int nKONTENEROW, int LADOWNOSC, int WartoscMIN, int WartoscMAX, int CiezarMIN, int CiezarMAX );

Element * WskElement;
Kombinacja * WskKombinacja;
Wynik * WynikBF, * WynikAlgZach, * WynikAlgDyn;



class Wynik
{
public:
    int CZAS, CIEZAR, WARTOSC;
   
    Wynik( int czas, int ciezar, int wartosc )
    {
        CZAS = czas;
        CIEZAR = ciezar;
        WARTOSC = wartosc;
    };
   
    ~Wynik()
    {
    };
};

class Element
{
public:
    int Value;
    Element * NEXT;
    Element * PREV;
   
    Element( int Val, Element * prv )
    {
        Value = Val;
        PREV = prv;
        NEXT = NULL;
    };
   
    ~Element()
    {
    };
};

class Kombinacja
{
public:
    Element * FIRST;
    Element * LAST;
    Element * NEWBIE;
    Element * CURRENT;
   
    int CIEZAR;
    int WARTOSC;
   
    Kombinacja()
    {
        FIRST = NULL;
        LAST = NULL;
        CIEZAR = 0;
        WARTOSC = 0;
    };
   
    ~Kombinacja()
    {
    };
   
    void AddElement( int Value )
    {
        if( FIRST == NULL )
        {
            FIRST = new Element( Value, FIRST );
            LAST = FIRST;
            CIEZAR += KontenerCiezar[ Value ];
            WARTOSC += KontenerWartosc[ Value ];
        } else
        {
            NEWBIE = new Element( Value, LAST );
            LAST->NEXT = NEWBIE;
            LAST = NEWBIE;
        };
    };
   
    void WriteAll()
    {
        CURRENT = FIRST;
        while( CURRENT != NULL )
        {
            cout << CURRENT->Value << " ";
            CURRENT = CURRENT->NEXT;
        }
       
        cout << endl;
    };
   
    void WriteWiC()
    {
        CURRENT = FIRST;
        cout << "Ciezar Wartosc" << endl;
        while( CURRENT != NULL )
        {
            cout << KontenerCiezar[ CURRENT->Value ] << " " << KontenerWartosc[ CURRENT->Value ] << endl;
            CURRENT = CURRENT->NEXT;
        }
       
        cout << endl;
    };
   
    int WartoscKombinacji()
    {
        return WARTOSC;
    };
   
    int CiezarKombinacji()
    {
        return CIEZAR;
    };
};

void kolor( int kk )
{
    SetConsoleTextAttribute( GetStdHandle( STD_OUTPUT_HANDLE ), kk );
}

void nadpis( const int xxxvv, const int yyyvv )
{
    HANDLE hCon = GetStdHandle( STD_OUTPUT_HANDLE );
    COORD coord = { xxxvv, yyyvv };
    SetConsoleCursorPosition( hCon, coord );
}

int max( int a, int b )
{
    if( a > b )
         return a;
    else
         return b;
   
}

void Heapify( int heap_size, int i )
{
   
    int l = 2 * i;
    int r = 2 * i + 1;
    int max = i;
    if( l < heap_size && WartosciWazone[ l ] > WartosciWazone[ max ] )
         max = l;
   
    if( r < heap_size && WartosciWazone[ r ] > WartosciWazone[ max ] )
         max = r;
   
    if( max != i )
    {
        podmien_elementy( & WartosciWazone[ max ], & WartosciWazone[ i ] );
        podmien_elementy( & WartosciWazoneINDEX[ max ], & WartosciWazoneINDEX[ i ] );
        Heapify( heap_size, max );
    }
}

void buduj_kopiec( int HeapSize )
{
    for( int i = HeapSize / 2; i >= 0; i-- )
         Heapify( HeapSize, i );
   
}

INT64 HS( int size )
{
    INT64 start, end;
    int n = size;
   
    /*
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazone[i]<<" ";
                            cout<<endl;
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazoneINDEX[i]<<" ";
                            cout<<endl;
                            getch();
                        */
   
    start = clock();
   
    buduj_kopiec( n );
    for( int i = n - 1; i >= 0; i-- )
    {
        podmien_elementy( & WartosciWazone[ i ], & WartosciWazone[ 0 ] );
        podmien_elementy( & WartosciWazoneINDEX[ i ], & WartosciWazoneINDEX[ 0 ] );
        n--;
        Heapify( n, 0 );
    }
    /*
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazone[i]<<" ";
                            cout<<endl;
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazoneINDEX[i]<<" ";
                            cout<<endl;
                            getch();
                        */
    end = 1000 *( clock() - start ) / CLOCKS_PER_SEC;
    return( end );
}



void generuj_zbior( int nKONTENEROW, int WartoscMIN, int WartoscMAX, int CiezarMIN, int CiezarMAX )
{
    //cout<<"Ciezar|Wartosc"<<endl;
    for( int i = 0; i < nKONTENEROW; i++ )
    {
        if( CiezarMAX - CiezarMIN != 0 )
             KontenerCiezar[ i ] =( rand() %( CiezarMAX - CiezarMIN + 1 ) ) + CiezarMIN;
        else KontenerCiezar[ i ] = CiezarMAX;
       
        if( WartoscMAX - WartoscMIN != 0 )
             KontenerWartosc[ i ] =( rand() %( WartoscMAX - WartoscMIN + 1 ) ) + WartoscMIN;
        else KontenerWartosc[ i ] = WartoscMAX;
       
        //cout<<KontenerCiezar[i]<<" "<<KontenerWartosc[i]<<endl;
       
    }
   
}

void BestDynamo( int Ladownosc, int nKONTENEROW )
{
   
    int start, end;
    start = clock();
    int ** tablica = new int *[ nKONTENEROW + 1 ];
    for( int i = 0; i <= nKONTENEROW; i++ )
         tablica[ i ] = new int[ Ladownosc + 1 ];
   
    for( int i = 0; i <= nKONTENEROW; i++ )
    {
       
        for( int l = 0; l <= Ladownosc; l++ )
        {
            if( i == 0 ) tablica[ i ][ l ] = 0;
            else if( l == 0 ) tablica[ i ][ l ] = 0;
            else if( l < KontenerCiezar[ i - 1 ] ) tablica[ i ][ l ] = tablica[ i - 1 ][ l ];
            else tablica[ i ][ l ] = max( tablica[ i - 1 ][ l - KontenerCiezar[ i - 1 ] ] + KontenerWartosc[ i - 1 ], tablica[ i - 1 ][ l ] );
           
            /*
            cout<<tablica[i][l]<<" ";
            getch();
            */
        }
       
        //cout<<endl;
    }
   
    for( int i = 0; i <= nKONTENEROW; i++ )
         delete[] tablica[ i ];
   
    delete[] tablica;
   
    end = clock() - start;
    WynikAlgDyn = new Wynik( end, 0, tablica[ nKONTENEROW ][ Ladownosc ] );
   
}

void BestBruteForce( int Ladownosc, int nKONTENEROW )
{
    int start, end;
    start = clock();
   
    Kombinacja * BEST, * NEWBIE;
    BEST = new Kombinacja();
   
    for( int unsigned i =( 1 << nKONTENEROW ); --i; )
    {
       
        NEWBIE = new Kombinacja();
       
        for( int unsigned k = 0; k < nKONTENEROW && NEWBIE->CiezarKombinacji() <= Ladownosc; k++ )
        {
            if(( i >> k ) & 1 ) NEWBIE->AddElement( k );
           
        }
       
        if( NEWBIE->CiezarKombinacji() <= Ladownosc && BEST->WartoscKombinacji() < NEWBIE->WartoscKombinacji() )
        {
            delete BEST;
            BEST = new Kombinacja();
            * BEST = * NEWBIE;
            //BEST->WriteWiC();
            //cout<<endl<<endl;
        };
       
        delete NEWBIE;
    }
   
   
   
   
   
    end = clock() - start;
    WynikBF = new Wynik( end, BEST->CiezarKombinacji(), BEST->WartoscKombinacji() );
    delete BEST;
   
   
}

void BestAlgZachlanny( int Ladownosc, int nKONTENEROW )
{
    int start, end;
    start = clock();
   
    Kombinacja * blabla;
    blabla = new Kombinacja();
   
    int MaxCiezar = 0;
    int MaxValue = 0;
    WykonajWartosciWazone( nKONTENEROW );
    HS( nKONTENEROW );
    int i = nKONTENEROW - 1;
   
    for( int i = nKONTENEROW - 1; MaxCiezar + KontenerCiezar[ WartosciWazoneINDEX[ i ] ] <= Ladownosc && i >= 0; i-- )
    {
        MaxValue += KontenerWartosc[ WartosciWazoneINDEX[ i ] ];
        MaxCiezar += KontenerCiezar[ WartosciWazoneINDEX[ i ] ];
        blabla->AddElement( WartosciWazoneINDEX[ i ] );
    }
    end =( clock() - start );
    WynikAlgZach = new Wynik( end, blabla->CiezarKombinacji(), blabla->WartoscKombinacji() );
   
}

void WykonajWartosciWazone( int nKONTENEROW )
{
    for( int i = 0; i < nKONTENEROW; i++ )
    {
        WartosciWazone[ i ] = KontenerWartosc[ i ] / KontenerCiezar[ i ];
        WartosciWazoneINDEX[ i ] = i;
        //cout<<WartosciWazone[i]<<" ";
    }
   
}


int zastap_element( int * zastepowany, int * tymzastapiony )
{
    * zastepowany = * tymzastapiony;
}

void podmien_elementy( int * x, int * y )
{
    int temp;
    temp = * x;
    * x = * y;
    * y = temp;
}



int main()
{
    int LADOWNOSC = 300;
    int nKONTENEROW = 50;
    int WartoscMIN = 50;
    int WartoscMAX = 500;
    int CiezarMIN = 20;
    int CiezarMAX = 50;
   
    nadpis( 8, 0 ); cout << "Czas [ms]";
    nadpis( 25, 0 ); cout << "| Wartosc";
    nadpis( 35, 0 ); cout << "| Ciezar";
    nadpis( 44, 0 ); cout << "| BladWzgledny";
    nadpis( 59, 0 ); cout << "| KONTENEROW";
    nadpis( 72, 0 ); cout << "| LADOWNOSC";
   
    nadpis( 2, 1 );
    kolor( 5 ); cout << "BF";
    nadpis( 8, 1 );
    kolor( 6 ); cout << "AlgZach ";
    nadpis( 17, 1 );
    kolor( 7 ); cout << "AlgDyn ";
   
    int pocz = 20;
    int kk = 4;
    for( int i = 50; i < LADOWNOSC; i += 5 )
    for( int j = pocz; j < nKONTENEROW; j += 1 )
    {
       
        generuj_zbior( j, WartoscMIN, WartoscMAX, CiezarMIN, CiezarMAX );
        BestBruteForce( i, j );
        BestAlgZachlanny( i, j );
        BestDynamo( i, j );
       
        nadpis( 1, kk );
        cout << WynikBF->CZAS;
        nadpis( 9, kk );
        cout << WynikAlgZach->CZAS;
        nadpis( 17, kk );
        cout << WynikAlgDyn->CZAS;
       
        nadpis( 26, kk );
        cout << WynikBF->WARTOSC << "|" << WynikAlgZach->WARTOSC << "|" << WynikAlgDyn->WARTOSC;
       
        nadpis( 42, kk );
        cout << WynikBF->CIEZAR << "|" << WynikAlgZach->CIEZAR << "|" << WynikAlgDyn->CIEZAR;
       
        nadpis( 55, kk );
        cout << float(( float( WynikAlgDyn->WARTOSC ) - float( WynikAlgZach->WARTOSC ) ) / float( WynikAlgDyn->WARTOSC ) );
       
        if( kbhit() )
        {
            cout << "pause";
            getch();
            cout << "\b\b\b\b\b     ";
        }
        delete WynikAlgDyn;
        delete WynikBF;
        delete WynikAlgZach;
        //getch();
       
        kk++;
    };
   
   
   
   
    return 0;
}