Spots et slots — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Spots et slots

Le sac de valeur maximum · niveau 2

Énoncé

On reprend la société de diffusion du cours, avec ses dix spots :

$d = [20, 20, 70, 10, 10, 40, 10, 80, 10, 40], g = [25, 25, 65, 15, 5, 35, 15, 75, 15, 45] .$

Vérifier à la main que, pour un slot de $T = 100$ secondes, le commercial obtient un gain de $100$ .
Le slot passe à $T = 120$ secondes. Quel est le gain du commercial, quel est le gain maximum, quels spots diffuser ?
Comment obtenir, en un seul calcul, les gains maximum de tous les slots de durées $T = 0, 10, \dots, 150$ ? Les donner.

Par gains décroissants, le commercial diffuse le spot $7$ ( $75$ , $80$ secondes), puis il reste $20$ secondes : le spot $2$ ( $70$ s), le spot $9$ et le spot $5$ ( $40$ s) ne tiennent pas, le spot $0$ ( $25$ , $20$ s) tient. Le slot est plein, gain $75 + 25 = 100$ .
Avec $T = 120$ , le commercial diffuse les spots $7$ ( $75$ ), $9$ ( $45$ ) : $120$ secondes, gain $120$ . Le gain maximum est $145$ , avec les spots $0, 1, 3, 4, 6, 8, 9$ (durées $20 + 20 + 10 + 10 + 10 + 10 + 40 = 120$ , gains $25 + 25 + 15 + 5 + 15 + 15 + 45 = 145$ ).
Il suffit d'un seul calcul, avec la plus grande contenance : la dernière ligne $M [n] [\cdot]$ du tableau calculé pour $C = 150$ donne $m (n, t)$ pour toutes les contenances $t \leq 150$ .


int[][] M = calculerM(g, d, 150);
for (int t = 0; t <= 150; t += 10)
    System.out.print(t + ":" + M[10][t] + " ");


0:0 10:15 20:30 30:45 40:55 50:70 60:80 70:95 80:100 90:115 100:125 110:140 120:145 130:150 140:160 150:175