Problème — Sac à dos avec reconstruction des objets

On remplit d'abord la table $K(i,c)$ comme précédemment. Pour reconstruire la sélection, on parcourt la table à rebours : à chaque étape, si $K(i,c)\ne K(i-1,c)$, c'est que l'objet $i$ a été pris, et l'on diminue la capacité de son poids.

def sac_a_dos_objets(poids, valeurs, capacite):
    n = len(poids)
    table = [[0] * (capacite + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(capacite + 1):
            if poids[i - 1] > c:
                table[i][c] = table[i - 1][c]
            else:
                table[i][c] = max(
                    table[i - 1][c],
                    valeurs[i - 1] + table[i - 1][c - poids[i - 1]]
                )
    # Reconstruction
    objets = []
    c = capacite
    for i in range(n, 0, -1):
        if table[i][c] != table[i - 1][c]:
            objets.append(i - 1)
            c -= poids[i - 1]
    objets.reverse()
    return table[n][capacite], objets

La complexité reste $O(n\times C)$ pour le remplissage, et la reconstruction se fait en $O(n)$.