[ALGO] Complexite des algorithmes (11)

valeurs de pieces
montant a rendre

11 facons :

= le nombre de facons de rendre avec les permieres pieces

On note les valeurs de pieces



= on prend les pieces
= on ignore les pieces

0 1 2 3 4 5 6 7 8 9 10
0 1 0 0 0 0 0 0 0 0 0 0
5c 1 1 0 0 0 0 1 0 0 0 0 1
2c 2 1 0 1 0 1 1 1 1 1 1 2
10c 3 1 0 1 0 1 1 1 1 1 1 3
1c 4 1 1 2 2 3 4 5 6 7 8 11
unsigned cc(const unsigned *values, unsigned count, unsigned amount)
{
    unsigned *res = calloc(amount + 1, sizeof *res);
    res[0] = 1;
    for (unsigned i = 0; i < count; i++)
    {
        unsigned val = values[i];
        for (unsigned j = val; j < amount; j++)
        res[j] += res[j - val];
    }
    unsigned r = res[amount];
    free(res);
    return r;
}

Algos

Outils pour la complexite