Esercizio in c++ indicazioni help me!!

[minomic]

Il vettore binario non lo carichi da input: è noto a priori.
Sì, per partire da destra devi utilizzare gli indici e devi conoscere la dimensione dell'array.
Ogni combinazione corrisponde a una certa somma: tu devi trovare quella minima, ma che sia superiore alla soglia per non far arrabbiare la nonna.

Per facilitarti (spero) ho scritto un po' di codice, che svolge già alcune delle funzioni. Cerca di capirlo bene e soprattutto di completarlo.

#include <iostream>
#include <cstdlib>
#include <cmath>

/* la dimensione dei due vettori
   se non e' fissata a priori, cambia questa parte */
const int size = 5;

/* ci saranno modi migliori per fare questa
   cosa, ma questo dovrebbe funzionare */
void prossima_combinazione(int* vettore) {
    int pos = size - 1;
    while(pos >= 0 && vettore[pos] == 1) {
        vettore[pos] = 0;
        pos--;
    }
    if(pos >= 0) {
        vettore[pos] = 1;
    }
}


void stampa_vettore(int* vettore) {
    for(int i=0; i<size; ++i) {
        std::cout << vettore[i] << "  ";
    }
    std::cout << std::endl;
}


/* punto chiave: calcola la somma delle portate che corrispondono
   a un elemento pari a 1 nel vettore binario */
int somma_portate_da_mangiare(int* portate, int* binario) {
    int somma = 0;
    for(int i=0; i<size; ++i) {
        if(binario[i] == 1) {
            somma += portate[i];
        }
    }
    return somma;
}


int main(int argc, char const *argv[])
{
    int portate[] = {3, 6, 4, 10, 15};
    int soglia = 12;
    int binario[] = {0, 0, 0, 0, 0};

    /* stampo tutte le combinazioni (con almeno un 1)
       tanto per vedere che sia tutto corretto */
    for(int i=0; i < pow(2, size) - 1; ++i) {
        prossima_combinazione(binario);
        stampa_vettore(binario);
    }

    // TODO
    /*
    - elimina la stampa sopra
    - fai un ciclo
    - per ogni combinazione calcoli la somma delle portate
    - se e' minore della soglia minima allora la scarti perche'
      farebbe arrabbiare la nonna
    - se e' maggiore del limite... qui vedi tu!

    Consiglio: devi trovare quella piu' piccola ma che sia maggiore del limite!
    */

    return 0;
}

Disclaimer: l'ho scritto molto al volo, quindi non escludo errori, anche enormi. Se lo usi (e lo consegni all'insegnante) lo fai sotto la tua responsabilita!

[Aleb65]

Intanto grazie mille per il codice che mi ha aiutato a capire meglio le operazioni.. però non capisco perchè non inserisci da input il numero delle portare,k e il vettore delle portate e le dai già scontate.. e il vettore binario lo hai inizializzato a tutti 0 mentre prima mi avevi detto che l'ultimo era 1...vabbè forse ti sarai confuso.. cmq io da quel che ho capito dalla traccia il programma deve fare queste combinazioni e di ognuna di queste deve farne la somma e allo stesso tempo salvare il valore delle portate perchè alla fine sono quelli che dobbiamo dare in output e non la somma delle portate.
Quindi verifica se questo pseudocodice va bene:

inserisci num portate,k,vettore portate
tutto in un ciclo da ora: esegui la parte di codice per le combinazioni
se elementovettore binario = 1 allora somma= somma+portate[i]
se somma>=k allora inserisci in un  altro vettore le portate che vanno bene che hai calcolato nella combinazione (fine ciclo)
alla fine si mostra in output il vettore delle portate giuste

che dici? E' giusto il mio procedimento o ho capito male qualcosa?

[minomic]

Intanto grazie mille per il codice che mi ha aiutato a capire meglio le operazioni.. però non capisco perchè non inserisci da input il numero delle portare,k e il vettore delle portate e le dai già scontate.. e il vettore binario lo hai inizializzato a tutti 0 mentre prima mi avevi detto che l'ultimo era 1...vabbè forse ti sarai confuso..

Osservazioni giuste, ma non mi sono confuso: l'ho messo tutto a zero così la funzione prossimaCombinazione mi restituisce [0, 0, ..., 0, 1]. Altrimenti avrei dovuto fare un caso particolare per il primo elemento della lista di combinazioni, mentre preferisco sempre che sia il codice a gestire tutto quanto, senza che io debba tenere a mente delle eccezioni.

Per quanto riguarda il caricamento dei vettori, che io dò per "scontati" hai assolutamente ragione: tu li devi caricare da input. Io ho inserito i valori da codice per fare prima, visto che non era quella la parte interessante che volevo mostrarti. Inoltre suppongo che tu non abbia difficoltà a riempire un vettore con numeri presi da input.

Il tuo pseudo-codice mi sembra sensato, ma manca una parte fondamentale: per decidere le portate giuste da mangiare devi senz'altro verificare che la somma sia >=K, ma devi anche trovare la combinazione con la somma MINIMA! Questa è una parte che nella tua idea non vedo...

Pensaci meglio, ma comunque ci siamo quasi.

[Aleb65]

si giusto evvero ci avevo pensato ma non l'ho scritto... bè su questo penso che sia facile : potrei ad esempio mettere tutte le somme giuste in un altro vettore che poi ne farei il minimo(questo lo so fare) però poi si complica la cosa di mostrare in output le portate giuste o forse mi è sfuggito qualche particolare di nuovo.. correggimi se sbaglio

[minomic]

In realtà puoi fare una cosa molto più semplice: ogni volta che trovi una combinazione accettabile (cioè tale per cui la somma è >=K) fai questo:
- se è la prima che incontri, allora la memorizzi come la migliore
- altrimenti la confronti con la migliore che hai salvato:
- se la somma è minore della migliore, allora questa diventa la nuova combinazione migliore (e la sostituisci)
- altrimenti la ignori perché è peggiore di quella che avevi salvato in precedenza

In questo modo ne memorizzi solo e sempre una. E' praticamente lo stesso algoritmo che si usa per trovare il minimo o massimo valore di un vettore.

[Aleb65]

giusto.. hai perfettamente ragione quindi questa operazione si potrebbe fare cosi:

procedura minimasomma
min= somma
in un ciclo(penso):se la  (seconda)somma trovata è minore di min allora somma=min

Per il salvataggio delle portate giuste in un vettore come lo posso fare? Lo posso fare subito dopo l'operazione " somma=min "??

[minomic]

Non c'è nessun ciclo ulteriore: è tutto dentro al ciclo con il quale "passi in rassegna" tutte le possibili combinazioni. Per quanto riguarda il come memorizzare la combinazione migliore, ti basta tenere un vettore chiamato (ad esempio) "binario_migliore" dove memorizzi (cioè ricopi) il vettore binario associato alla migliore combinazione delle portate.

[Aleb65]

In questo modo però ad esempio su 4 portate ,quelle estreme vanno bene stamperei " 1 0 0 1 ". Dovrei fare un altro processo di stampa del vettore con un if perchè dovrei prima controllare in tutti i posti del vettore se ci sono 1, e dovrei fare una stampa giocando sugli indici ,giusto? Ma come??

[minomic]

Premesso che secondo me il semplice vettore binario_migliore è una soluzione accettabile, se proprio vuoi anche stampare le singole portate che devono essere mangiate, allora puoi ovviamente fare un nuovo ciclo sul vettore delle portate e stampare un elemento solo se il corrispondente elemento nel vettore binario_migliore è pari a 1.

[Aleb65]

Per fare ciò dovrei fare in questo modo:

for(i=0;i<n;i++)
{
 if (binario_migliore[i]=1)
cout<<"Può essere mangiata portata <<i<<endl;
}

Ovviamente ci saranno più cout ma non fa niente...
Anche se ho scritto un altro tipo di stampa indicando solo la posizione delle portate giuste ,va bene lo stesso?