Algoritmi di ricerca e ottimizzazione

Problemi di ricerca e ottimizzazione

Principio di moltiplicazione

N decisioni in sequenza tra M diverse scelte possibili = costruzione di N-uple. Enumerare tutti i possibili menù di un ristorante, tenendo conto che un menù è composto da primo, secondo e dolce.

typedef struct { int scelte; int num_scelte; } Livello;

int princ_molt(Livello pos, Livello valori, int soluzione, int numerolivelli, int contatore) {
    if (pos == numerolivelli) {
        printf("\n{");
        for (int i = 0; i < numerolivelli; i++)
            printf("%d ", soluzione[i]);
        printf("}\n");
        return contatore + 1;
    }
    for (int i = 0; i < valori[pos].num_scelte; i++) {
        soluzione[pos] = valori[pos].scelte[i];
        contatore = princ_molt(pos + 1, valori, soluzione, numerolivelli, contatore);
    }
    return contatore;
}

typedef struct { int scelte; int num_scelte; } Livello;
void princ_molt_ottimo_R(int pos, Livello valori, int soluzione, int numerolivelli, int currValue, int bestValue, int bestSol) {
    if (pos == numerolivelli) {
        if (currValue > bestValue) {
            bestValue = currValue;
            for (int i = 0; i < numerolivelli; i++) { // aggiorna la soluzione migliore
                bestSol[i] = soluzione[i];
            }
        }
        return;
    }
    for (int i = 0; i < valori[pos].num_scelte; i++) {
        soluzione[pos] = valori[pos].scelte[i];
        princ_molt_ottimo_R(pos + 1, valori, soluzione, numerolivelli, currValue + valori[pos].scelte[i], bestValue, bestSol);
    }
}

void princ_molt_ottimo(Livello valori, int soluzione, int numero_livelli) {
    int bestSol = calloc(numero_livelli, sizeof(int));
    int bestValue = 0;
    princ_molt_ottimo_R(0, valori, soluzione, numero_livelli, 0, &bestValue, bestSol);
    printf("Elemento ottimo:\n{");
    for (int i = 0; i < numero_livelli; i++) {
        printf("%d ", bestSol[i]);
    }
    printf("}\n");
    free(bestSol);
}

Disposizioni semplici

In quanti modi posso disporre n oggetti distinti in k posizioni = D_n,k. In quanti modi 3 finalisti si possono posizionare sul podio in 1^a, 2^a e 3^a posizione.

int disp(int pos, int valori, int soluzione, int mark, int numero_elementi, int classe, int contatore) {
    if (pos == classe) {
        printf("Item: ");
        for (int i = 0; i