05

Programmation dynamique

Exercice 1

Q 1.1

Q 1.2

• Si n est en monome:
  Alors tous les autres élèves peuvent être dans les autre configurations
• Si n est en binome:
  Alors il est nécessairement avec un autre élève. Il y aura alors configurations pour les autres élèves. Il peut e mettre avec (n-1) élèves, d’où le résultat.

Q 1.3

On en déduit que:

Q 1.4

t = [1, 2]

def nb(n):
  if len(t) > n:
    return t[n]

  tmp = nb(n-1) + (n-1) * nb(n-2)
  t.append(tmp)
  return tmp

def nb(n):
  t = [1, 2] + [0] * (n-2)

  for i in range(3, n+1):
    t[i] = t[i-1] + (i-1) * t[i-2]
  return t[n]

Exercice 2

Q 2.1

Avec valeurs de l’exemple, , stratégie gloutonne donne alors que la meilleure option est

Q 2.2

1.

le morceau maximal que l’on peut obtenir pour une corde de mètres

2.

, en initialisant

3.

DecoupeCorde(p,n)
  Entrée p[1..n] un tab de prix, avec p[i] = p_i
  sortie: Découpe optimale à partir d'une corde de longueur n
  L[0] <- 0
  pour i allant de 1 à n faire:
    r[i] <- - inf
    pour j allant de 1 à i faire:
      r[i] <- max(r[i]n r[i - j] + p[j])
  renvoyer p[n]

Q 2.3

DecoupeCorde(p,n)
  Entrée p[1..n] un tab de prix, avec p[i] = p_i
  sortie: Découpe optimale à partir d'une corde de longueur n
  L[0] <- 0
  pour i allant de 1 à n faire:
    r[i] <- - inf
    pour j allant de 1 à i faire:
      r[i] <- max(r[i]n r[i - j] + p[j])
  renvoyer p[n]

Exercice 3

Q 3.1

Q 3.2

pour i allant de n-1 à 1 faire
  opt[i] := + inf
  pour j allant de i + 1 à n faire
    si c [i, j] + opt[j] < opt[i] alors
      opt[0] := c[i, j] + opt[j]

Q 3.3

opt[n] := 0, S[n] := n

pour i allant de n-1 à 1 faire
  opt[i] := + inf
  pour j allant de i + 1 à n faire
    si c [i, j] + opt[j] < opt[i] alors
      opt[0] := c[i, j] + opt[j]
      s[i] := j

Exercice 4

Q 4.1

Page incomplète ou erronée? Contribuez sur le repo