Quand la contenance est immense — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Quand la contenance est immense

Le sac de valeur maximum · niveau 3 (difficile)

Énoncé

Le calcul du cours est en $Θ (n C)$ . Avec $C = 1 0^{9}$ (des tailles en octets, par exemple), il est inutilisable.

Expliquer pourquoi on dit que cette complexité est pseudo-polynomiale.
On suppose les valeurs petites. On note $w (k, v)$ la taille minimum d'un sous-ensemble des $k$ premiers objets de valeur exactement $v$ ( $+ \infty$ s'il n'y en a pas). Donner l'équation de récurrence des $w (k, v)$ , puis la façon d'en déduire la valeur maximum d'un sac de contenance $C$ . Quelle est la complexité ?
Application : les objets du cours, avec des tailles multipliées par $1 0^{8}$ et $C = 1 0^{9}$ .

Corrigé

La taille d'une instance est le nombre de chiffres nécessaires pour l'écrire : la contenance $C$ s'écrit avec environ $lo g_{10} C$ chiffres. Un temps en $Θ (n C)$ est donc exponentiel en la taille de l'écriture de $C$ ; il n'est polynomial qu'en la valeur de $C$ .
On regarde le dernier objet. Base : $w (0, 0) = 0$ , $w (0, v) = + \infty$ pour $v \geq 1$ . Hérédité :

$w (k, v) = min {w (k - 1, v), t_{k - 1} + w (k - 1, v - v_{k - 1})},$

le second terme n'existant que si $v_{k - 1} \leq v$ . La valeur maximum d'un sac de contenance $C$ est le plus grand $v$ tel que $w (n, v) \leq C$ . Avec $V = \sum v_{i}$ , le calcul est en $Θ (n V)$ : indépendant de $C$ .

Avec $V = [11, 4, 5, 4, 4]$ ( $V = 28$ ), le tableau $W$ n'a que $6 \times 29$ cases, même pour $C = 1 0^{9}$ ; les tailles sont stockées dans des long. Le programme retrouve la valeur $13$ , comme avec les petites tailles.