def knapsack2(p, v, cmax):
    """Knapsack problem: select maximum value set of items if total size not more than capacity.
    alternative implementation with same behavior.

    :param p: table with size of items
    :param v: table with value of items
    :param cmax: capacity of bag
    :requires: number of items non-zero
    :returns: value optimal solution, list of item indexes in solution
    :complexity: O(n * cmax), for n = number of items
    """
    n = len(p)
    # Plus grande valeur obtenable avec objets ≤ i et capacité c
    pgv = [[0] * (cmax + 1) for _ in range(n)]
    for c in range(cmax + 1):  # Initialisation
        pgv[0][c] = v[0] if p[0] >= c else 0
    pred = {}  # Prédécesseurs pour mémoriser les choix faits
    for i in range(1, n):
        for c in range(cmax + 1):
            pgv[i][c] = pgv[i - 1][c]  # Si on ne prend pas l'objet i
            pred[(i, c)] = (i - 1, c)
            # Est-ce que prendre l'objet i est préférable ?
            if c >= p[i] and pgv[i - 1][c - p[i]] + v[i] > pgv[i][c]:
                pgv[i][c] = pgv[i - 1][c - p[i]] + v[i]
                pred[(i, c)] = (i - 1, c - p[i])  # On marque le prédécesseur
    # On pourrait s'arrêter là, mais si on veut un sous-ensemble d'objets
    # optimal, il faut remonter les marquages
    cursor = (n - 1, cmax)
    chosen = []
    while cursor in pred:
        # Si la case prédécesseur a une capacité inférieure
        if pred[cursor][1] < cursor[1]:
            # C'est qu'on a ramassé l'objet sur le chemin
            chosen.append(cursor[0])
        cursor = pred[cursor]
    if cursor[1] > 0:  # A-t-on pris le premier objet ?
        # (La première ligne n'a pas de prédécesseur.)
        chosen.append(cursor[0])
    return pgv[n - 1][cmax], chosen
dataset/ETHPy150Open jilljenn/tryalgo/tryalgo/knapsack.py/knapsack2/swapped operands of `>=`