[alg/c++]grootste uit een array onder 1 voorwaarde

[Verwijderd]

Ten eerst, sorry voor de vage titel, ik kon niks beters bedenken .

Maar het zit zo, ik heb een array van 9 willekeurige signed int's, dus bv:

code:

a[0]=5
a[1]=10
a[2]=5
a[3]=20
a[4]=10
a[5]=5
a[6]=10
a[7]=20
a[8]=10

De eerste 3 stellen de inhoud voor van afvalbak #1, de volgende 3 van afvalbak #2, en de laatste 3 van afvalbak #3.
Daarin weer stelt het eerste element(dus 0, 3 en 6) het aantal groene flessen voor, 1, 4 en 7 het aantal bruine flessen en 2, 5 en 8 het aantal niet gekleurde flessen.

Nu moet voor een willekeurige aantal flessen uitrekenen met hoeveel zetten ik alles goed kan sorteren(dus bak1 alleen groen, bak2 alleen bruin of andersom, maakt niet uit hoe, als het maar bij elkaar zit). Ik ben al een heel eind, maar ik sta nu voor een probleem, het minst aantal zetten krijg je door de grootste aantal van de drie groene, bruine en niet gekleurde te laten staan.

Maar dat lukt niet altijd, want soms zitten de meeste per groep in 1 bak, zoals bij mijn voorbeeld het geval is. Van groen zitten de meeste in bak 2(a[3]). Maar van bruin en niet gekleurd zitten de meeste in bak 3, dus van 1 van de 2 moet ik de 1 na grootste nemen. En dat wil niet. Ik het volgende:

C++:

int biggest(const int a, const int b)
{
    int buffer=0;
    unsigned int returnValue = 0;
    for(int i=a; i<=b; i += 3)
    {
        if(*(invoer+i)>buffer)
        {
            buffer = *(invoer+i);
            returnValue = i;
        }
    }
        return returnValue;
}

a, b en c zijn hier de indexen van de array invoer.

Ik roep dit 3 keer aan

C++:

    bin1.biggest = biggest(0, 6);
    bin2.biggest = biggest(1, 7);
    bin3.biggest = biggest(2, 8);

Nu is mijn vraag dus, hoe kan ik kijken of de waardes die worden gereturnd, in 1 bak zitten, en zoja hoe kan ik dan de 1 na grootste krijgen?

[ Voor 3% gewijzigd door Verwijderd op 01-02-2004 12:14 ]

[Macros]

Eerst 1 opmerking. Je had het jezelf een stuk makkelijker gemaakt als je structs of classes had gebruikt, ipv een array waarin alles staat en dat het afhankelijk is van waar iets staat voor wat het is. Dat maakt je code erg onleesbaar op waarschijnlijk heel wat plekken.

[Verwijderd]

hoe bedoel je, dat ik dus bijv een struct BIN had gemaakt, en dan bin1, bin2 en bin3 had, en daarin de elementen stopte?

[Verwijderd]

na 3 dagen mn hersens gekraakt te hebben is het gelukt
en om de lay out niet te verneuken een linkje met de oplossing voor de liefhebbers en geintereseerden

http://rafb.net/paste/results/J1902219.html

[Soultaker]

Dit probleem dus: Ecological Bin Packing.

Ik had 'm zo opgelost:

C++:

#include <iostream>
using namespace std;

int main()
{
    int bin[3][3];

    while(cin >>
        bin[0][0] >> bin[0][2] >> bin[0][1] >> 
        bin[1][0] >> bin[1][2] >> bin[1][1] >> 
        bin[2][0] >> bin[2][2] >> bin[2][1])
    {
        const int perms[][3] =
        {
            { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 },
            { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 }
        };
        int best_p = 0, best_moves = 2147483647;

        for(int p = 0; p < 6; ++p)
        {
            int moves = 0;
            for(int b = 0; b < 3; ++b)
                for(int c = 0; c < 3; ++c)
                    if(c != perms[p][b])
                        moves += bin[b][c];
            if(moves < best_moves)
            {
                best_p = p;
                best_moves = moves;
            }           
        }

        cout << ("BCG"[perms[best_p][0]]) << ("BCG"[perms[best_p][1]]) <<
            ("BCG"[perms[best_p][2]]) << ' ' << best_moves << '\n';
    }
}

[Macros]

Nice, je hebt de standaard bruteforce methode geimplementeerd
Niks mis mee

[Verwijderd]

En wat kan nog geoptimaliseerd worden vinden jullie?

[Soultaker]

Moeilijk te zeggen, als de URL niet meer naar je code verwijst.

Ik kan me herinneren dat je oplossing nogal lang was. Beetje onnodig voor zo'n simpel probleem. Verder is het probleem zo beperkt dat eigenlijk alle code wel goed genoeg werkt; je kunt met wat handige constructies wel hier en daar wat lusjes besparen maar of je code nu O(N³), O(N⁴) of O(N¹⁰) is maakt nauwelijks uit, als N maar klein genoeg is (3, in dit geval).

[Verwijderd]

ja ok, maar dat heb ik altijd dat ik de simpelste dingen met een grote omweg uitwerk.
Dit was trouwens mn code

C++:

#include <iostream>
#include <string>

#define green 'G'
#define brown 'B'
#define clear 'C'

using namespace std;

void convert_string_to_int(char*);

struct BIN
{
public:
    bool state;
    char color;
    int moves, content[3], use;
};

int * invoer;

int main(void)
{
    BIN bin1, bin2, bin3;
    char string[99]={'*'};
    bin1.state = false; bin2.state = false; bin3.state = false;

    cin.getline(&string[0], 99, '\n');
    
    convert_string_to_int(string);
    

    bin1.content[0] = *invoer;
    bin1.content[1] = *(invoer+1);
    bin1.content[2] = *(invoer+2);

    bin2.content[0] = *(invoer+3);
    bin2.content[1] = *(invoer+4);
    bin2.content[2] = *(invoer+5);

    bin3.content[0] = *(invoer+6);
    bin3.content[1] = *(invoer+7);
    bin3.content[2] = *(invoer+8);

    for(int i=0; i<3; i++)
    {
        if(bin1.content[i] >= bin2.content[i])
        {
            if(bin1.content[i] >= bin3.content[i])
            {
                if(!bin1.state)
                {
                    bin1.state = true;
                    bin1.use = i;
                }
                else if(bin2.content[i] >= bin3.content[i])
                {
                    bin2.state = true; 
                    bin2.use = i;
                }
                else
                {
                    bin3.state=true;
                    bin3.use = i;
                }
            }
            else
            {
                if(!bin3.state)
                {
                    bin3.state = true;
                    bin3.use = i;
                }
                else if(!bin1.state)
                {
                    bin1.state = true;
                    bin1.use = i;
                }
                else
                {
                    bin2.state = true;
                    bin2.use = i;
                }
            }
        }
        else if(bin1.content[i] < bin2.content[i])
        {
            if(bin2.content[i] <= bin3.content[i])
            {
                if(!bin3.state)
                {
                    bin3.state = true;
                    bin3.use = i;
                }
                else if(!bin2.state)
                {
                    bin2.state = true;
                    bin2.use = i;
                }
                else
                {
                    bin1.state = true;
                    bin1.use =i;
                }
            }
            else if(bin2.content[i] > bin3.content[i])
            {
                if(!bin2.state)
                {
                    bin2.state = true;
                    bin2.use = i;
                }
                else if(!bin3.state)
                {
                    bin3.state = true;
                    bin3.use = i;
                }
                else
                {
                    bin1.state = true;
                    bin1.use = i;
                }
            }
        }
        
    }

    bin1.moves = bin2.content[bin1.use] + bin3.content[bin1.use];
    bin2.moves = bin1.content[bin2.use] + bin3.content[bin2.use];
    bin3.moves = bin1.content[bin3.use] + bin2.content[bin3.use];
    
    if(!bin1.use)
        bin1.color = green;
    else if(bin1.use == 1)
        bin1.color = brown;
    else
        bin1.color = clear;

    if(!bin2.use)
        bin2.color = green;
    else if(bin2.use == 1)
        bin2.color = brown;
    else
        bin2.color = clear;

    if(!bin3.use)
        bin3.color = green;
    else if(bin3.use == 1)
        bin3.color = brown;
    else
        bin3.color = clear;

    cout<<bin1.color<<bin2.color<<bin3.color<<" "<<bin1.moves+bin2.moves+bin3.moves<<endl;
    
    delete[] invoer;
    return 0;
}


void convert_string_to_int(char temp[99])
{
    char input[9][11];
    int counter=0;
    invoer = new int[9];
    
    for(int i=0; i<99; i++)
    {
        if(temp[i] != 0)
            counter++;
    }
    
    int x=0;
    int error_counter =0;
    for(i=0; i<9; i++)
    {
        int j=0;
        while(temp[x] != 32 && temp[x] != 0)
        {
            
            error_counter = 0;
            while(j<10) 
            {
                input[i][j] = temp[x];
                j++;
                break;
            }
            x++;
        }
        x++;
        error_counter++;
        if(error_counter>1)
            break;
    }
    
    i = 0;
    while(input[i][0] > 0 && i<9)
    {
        invoer[i] = atoi(input[i]);
        i++;
    }
}