Sac à dos 0/1

let sac objets capacite =
  let n = Array.length objets in
  let dp = Array.make_matrix (n + 1) (capacite + 1) 0 in
  for i = 1 to n do
    let (po, va) = objets.(i - 1) in
    for w = 0 to capacite do
      dp.(i).(w) <- dp.(i - 1).(w);
      if po <= w && dp.(i - 1).(w - po) + va > dp.(i).(w) then
        dp.(i).(w) <- dp.(i - 1).(w - po) + va
    done
  done;
  dp.(n).(capacite)

dp.(i).(w) est la meilleure valeur avec les i premiers objets sous capacité w : on choisit, pour l'objet i, le meilleur entre « sans » et « avec ». Coût $\Theta (nW)$. Le glouton par ratio (chapitre 12) ne donnait pas cet optimum.