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