+ Rispondi al Thread
Visualizzazione dei risultati da 1 a 5 su 5

Discussione: Algoritmo first-fit per bin-packing

  1. #1
    L'avatar di Windows M
    Windows M non è in linea Scolaretto
    Post
    319

    Algoritmo first-fit per bin-packing

    Ciao a tutti ,
    è da tempo che non scrivo più sul forum, però proprio ieri mi sono trovato a dover risolvere durante una gara un problema (questo) di tipo algoritmico che ho subito riconosciuto essere una qualche variante del problema del bin-packing.

    L'ho risolto con l'euristica first fit - il Cormen (non me ne vogliano gli altri 3 autori) conferma che si tratti di un problema NP-Hard, quindi un'euristica mi sembra più che ragionevole - solo che per input relativamente "grandi", dell'ordine di 10^5 elementi, risulta troppo lento (il caso particolare è un input lungo 100k con elementi tutti uguali a 3).

    Qui il mio codice (tipico da gara, quindi alcune cose sono inguardabili dal punto di vista stilistico):
    codice:
    #include <fstream>
    #include <iostream>
    #include <algorithm>
    #define MAX_N 100005
    
    using namespace std;
    
    int n;
    int s[MAX_N];
    int qty[MAX_N+1];
    
    int count_taxi()
    {
        //order them...
        int count=1;
    
        sort(s, s+n, std::greater<int>());
    
        for(int i=0; i < n; i++)
        {
            bool found=false;
            for(int j=0; j < count;j++)
            {
                if(qty[j]+s[i] <= 4)
                {
                    qty[j]+=s[i];
                    found=true;
                    break;
                }
            }
            if(!found)
            {
                //cout << "!found" << endl;
                qty[count++]=s[i];
            }
        }
        return count;
    }
    
    int main()
    {
        #ifdef DEBUG
        ifstream cin("input.txt");
        #endif
    
        cin >> n;
    
        for(int i=0; i < n; i++)
            cin >> s[i];
    
        cout << count_taxi() << endl;
        return 0;
    }
    Grazie
    CiaoCiao.
    Se in un primo momento l'idea non è assurda, allora non c'è nessuna speranza che si realizzi. [Albert Einstein]

    A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. [G.H.Hardy]

  2. #2
    Luogo
    Granducato di Toscana
    Post
    836
    Blogs
    51
    Vedo soltanto ora il thread.
    Si tratta di un problema fortemente vincolato, che per natura va affrontato con una strategia tipo pigeonhole. Non occorre occupare memoria con array di dimensioni esorbitanti: il problemino si risolve in tempo costante ammortizzato (la sola lettura dei dati è proporzionale alla dimensione dell'input) e con una occupazione fissa (= indipendente dall'input) di memoria, pari a quattro interi non segnati, e senza alcun loop.

    Infatti, esistono solamente quattro possibili valori per l'ampiezza del gruppo di studenti, pertanto la lettura si può effettuare come nello shellsort o nel conteggio dei caratteri ASCII da un testo arbitrario, ossia indirizzando direttamente l'array delle occorrenze col dato appena letto, dopo un ovvio quanto minimale controllo di congruenza formale.
    Ecco un (pessimo, ma sbrigativo) esempio da manuale:

    codice:
    int main(void)
    {
        int i, n, m;
        unsigned int students[MAX_VAL];
        
        memset(students, 0, MAX_VAL * sizeof(int));
        scanf("%d", &n);
        
        for (i = 0; i < n; ++i)
        {
            scanf("%d", &m);
            if ((m > 0) && (m < 5))
            {
                students[m -1] += 1;
            }
        }
        
        printf("Taxi necessari: %d\n\n", TaxiCount(students));
        
        return (0);
    }
    Una volta ottenuti questi quattro numeretti, che rappresentano completamente l'input in forma "compressa", non resta che ricombinarli. Ciò che dobbiamo ottenere è, in realtà, una soluzione ad un problemino di composizione (l'opposto della partizione di un intero...). Dobbiamo cioè sostanzialmente conteggiare quante composizioni, di valore pari a 4, possiamo ottenere con le quantità a nostra disposizione - con qualche piccola variante.

    Dato l'approccio seguito, mi pare però che qui occorra una spiegazione meno sintetica e più ad usum delphini. Le partizioni possibili, in questo caso, sono:

    Formula LaTeX: \begin{align*}\\4 &= 4\\&= 3+1\\&= 2+2\\&= 2+1+1\\&= 1+1+1+1\end{align*}

    Il che ci dà, in modo pressoché immediato, una formuletta lineare da applicare. Se infatti conveniamo di ignorare la composizione 2+1+1 (tranne in un caso specifico, che vedremo) in favore di quelle combinatorialmente equivalenti, abbiamo che il totale si compone di:
    • Tutti i gruppi di 4 studenti, conteggiati una sola volta (students[3] nell'esempio);
    • Tutti i gruppi di 3 studenti, conteggiati una sola volta (per la regola "all members of each group should ride in the same taxi"). Spiego meglio, perché qui si hanno tre sottocasi apparenti, secondo la relazione tra il numero di gruppi di tre studenti (diciamo S3) e quello dei singoli S1:
    a) S3 > S1: formeremo S1 taxi con 3+1 studenti e S3 - S1 taxi con 3 studenti, dovendo conteggiare quindi S1 + S3 - S1 = S3 taxi;
    b) S3 = S1: Occorrono S3 taxi che porteranno 3+1 studenti.
    c) S3 < S1: Potremo formare solo S3 taxi del tipo 3+1.
    Appare palese come, in tutti e tre i casi, il contributo dei gruppi di 3 è tale che ad ogni gruppo corrisponde un taxi, esattamente come nel caso precedente.
    • Per i gruppi di due, conteggiamo la metà del numero disponibile, approssimata all'intero successivo se dispari. Consideriamo infatti di formare taxi con gruppi da 2+2, con eventuale avanzo di un gruppo (che può dare un caso particolare, gestito a parte).
    • Infine, per i singoli, dobbiamo tenere presente l'eventuale accoppiamento già effettuato con i gruppi da 3, con una sottrazione condizionata (è infatti palese che nel caso a) nulla di buono verrebbe dal sottrarre ad un numero naturale un distinto naturale maggiore di esso...). Gli eventuali singoli rimanenti verranno "stipati" a quattro a quattro negli ultimi taxi, con eventuale resto. E attenzione all'unico eventuale caso particolare: se tale "resto" è non nullo ma diverso da tre E il numero di gruppi di due è dispari, i singoli rimanenti si possono intruppare col duetto superstite in un taxi 2+1 o 2+1+1 e con ciò occorre diminuire di uno il totale fin qui ottenuto, per evitare un erroneo doppio conteggio.

    Tutto qui. Con un paio di operazioni algebriche, una if() e qualche operatore ternario abbiamo risolto elegantissimamente il problema, in tempo costante (a parte le triviali operazioni di input, ovviamente). Si noti anche la comoda idiv().

    codice:
    #include <stdlib.h>
    #include <stdio.h>
    #include <mem.h>
    
    #define MAX_VAL 4
    
    unsigned int idiv(unsigned int a, unsigned int b)
    {
        unsigned int q = a / b;
        q += a % b != 0 ? 1 : 0;
        return(q);
    }    
    
    int TaxiCount(unsigned int st[])
    {
        int i;
        int ret, t;
        
        for (i = 0; i < MAX_VAL; ++i)
        {
            printf("st[%d] = %d\n", i, st[i]);
        }
        
        /* 
        ** Le operazioni sono qui frazionate per ovvie motivazioni 
        ** didattiche e di comodita' di lettura/debug. 
        */
        ret = st[3] + st[2];
        ret += idiv(st[1], 2);
        st[0] -= min(st[2], st[0]);
        ret += idiv(st[0], 4);
        if ((st[1] & 1) && (st[0] % MAX_VAL > 0) && (st[0] % MAX_VAL < 3))
        {
            --ret;
        }
        return(ret);
    }
    
    int main(void)
    {
        int i, n, m;
        unsigned int students[MAX_VAL];
        
        memset(students, 0, MAX_VAL * sizeof(int));
        scanf("%d", &n);
        
        for (i = 0; i < n; ++i)
        {
            scanf("%d", &m);
            if ((m > 0) && (m < MAX_VAL +1))
            {
                students[m -1] += 1;
            }
        }
        
        printf("Taxi necessari: %d\n\n", TaxiCount(students));
        
        return (0);
    }

    Quote Originariamente inviato da Windows M Visualizza il messaggio
    ...il Cormen (non me ne vogliano gli altri 3 autori) conferma che si tratti di un problema NP-Hard
    Ho provveduto personalmente ad avvertire i professori Leiserson, Rivest e Stein che ti aspetteranno sotto casa armati di Taumaturgico Bastone™ per spiegarti il loro punto di vista sulla questione e insegnarti benevolmente che il loro Testo Sacro viene di norma citato amichevolmente come CLRS...
    Ultima modifica di M.A.W. 1968; 08-03-2012 19:07  Motivo: Aggiunto link
    Tutti gli utenti sono pregati di prendere visione del Regolamento del Forum e di rispettarlo.

    Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo... già che ci siete, leggete questa selezione di parole famose di alcuni tra i più grandi geni.

    • Un plauso a Grisha Perelman, raro esempio di genuino anticonformismo umano e scientifico.

  3. #3
    L'avatar di Windows M
    Windows M non è in linea Scolaretto
    Post
    319
    Parafrasando un noto matematico "questa viene direttamente dal Libro!", in ogni caso grazie infinite per la soluzione ed è un buon esempio di K.I.S.

    Un'ultima domanda:
    perchè nella condizione per il caso particolare utilizzi (s[1] & 1) e non semplicemente (s[1]%2==1) oppure !(s[1]%2)?

    Ho provveduto personalmente ad avvertire i professori Leiserson, Rivest e Stein che ti aspetteranno sotto casa armati di Taumaturgico Bastone™ per spiegarti il loro punto di vista sulla questione e insegnarti benevolmente che il loro Testo Sacro viene di norma citato amichevolmente come CLRS...
    Provvederò a fare una congrua penitenza imparando a memoria il Testo sacro sperando che i Professori siano clementi

    Grazie ancora
    Matteo.
    Se in un primo momento l'idea non è assurda, allora non c'è nessuna speranza che si realizzi. [Albert Einstein]

    A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. [G.H.Hardy]

  4. #4
    Luogo
    Granducato di Toscana
    Post
    836
    Blogs
    51
    Quote Originariamente inviato da Windows M Visualizza il messaggio
    perchè nella condizione per il caso particolare utilizzi (s[1] & 1) e non semplicemente (s[1]%2==1) oppure !(s[1]%2)?
    Perché è un idioma molto più elegante, e notevolmente più efficiente sulla maggior parte dei processori. Isolare il bit meno significativo richiede una istruzione booleana atomica, normalmente eseguita in un singolo ciclo di clock, mentre il modulo usualmente coinvolge istruzioni temporalmente disastrose, come la DIV su x86. Per giunta, molti compilatori non effettuano alcuna operazione aggiuntiva per trasformare il risultato in una costante logica, utilizzando direttamente il valore nel registro dopo l'AND.
    Tutti gli utenti sono pregati di prendere visione del Regolamento del Forum e di rispettarlo.

    Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo... già che ci siete, leggete questa selezione di parole famose di alcuni tra i più grandi geni.

    • Un plauso a Grisha Perelman, raro esempio di genuino anticonformismo umano e scientifico.

  5. #5
    L'avatar di Windows M
    Windows M non è in linea Scolaretto
    Post
    319
    Immaginavo ci fosse un motivo riguardante l'ottimizzazione

    Grazie.
    Se in un primo momento l'idea non è assurda, allora non c'è nessuna speranza che si realizzi. [Albert Einstein]

    A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. [G.H.Hardy]

+ Rispondi al Thread

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi