def compute_table(weights, values, p_max):
    num_objs = len(weights)

    # Allocation de la table : tableau à deux entrées : une ligne par objet,
    # une colonne par poids autorisé (<= p_max) ; à noter que l'on commence les
    # poids à 0, si bien que le poids correspond exactement à l'indice de
    # colonne et qu'il y a p_max+1 poids par ligne
    table = [None] * num_objs
    for i in range(0, num_objs):
        table[i] = [0] * (p_max+1)

    # Calcul de la première ligne
    for p in range(weights[0], p_max+1):
        table[0][p] = values[0]

    # Calcul des lignes suivantes
    for i in range(1, num_objs):
        for p in range(0, p_max+1):
            if weights[i] <= p:
                table[i][p] = max(table[i-1][p],
                                  table[i-1][p - weights[i]] + values[i])
            else:
                table[i][p] = table[i-1][p]
        print table[i]
    return table

def bag(weights, values, p_max):
    # Test d'intégrité des valeurs passées : weights doit être la liste des
    # poids des objets, values celle de leurs valeurs
    num_objs = len(weights)
    if len(values) != num_objs:
        raise ValueError("Il doit y avoit le même nombre de poids et de valeurs")
    for i in range(0, num_objs):
        if weights[i] < 0:
            raise ValueError("Un objet ne peut avoir un poids négatif ou nul")

    table = compute_table(weights, values, p_max)

    # Si table[i][p] == table[i-1][p] c'est que l'objet i n'a pas été ajouté
    # dans le sac de poids p. On commence par chercher le dernier objet ajouté
    # au sac, celui qui a permis d'atteindre la valeur maximale qui se trouve
    # en table[num_objs-1][p_max] ; on continue en enlevant le poids de cet
    # objet à p_max et en cherchant le dernier objet ajouté au sac qui a permis
    # d'atteindre la nouvelle valeur maximale ; etc.
    bag = []
    for i in range(num_objs-1, 0, -1):
        if table[i][p_max] != table[i-1][p_max]:
            bag.insert(0, i)
            p_max -= weights[i]

    # Pour finir on regarde si objet 0 rentre dans le sac
    if weights[0] <= p_max:
        bag.insert(0, 0)

    return bag