Source code for tryalgo.knapsack
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Knapsack
jill-jênn vie et christoph dürr - 2015-2019
"""
# snip{
[docs]
def knapsack(p, v, cmax):
"""Knapsack problem: select maximum value set of items if total size not
more than capacity
: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)
opt = [[0] * (cmax + 1) for _ in range(n + 1)]
sel = [[False] * (cmax + 1) for _ in range(n + 1)]
# --- basic case
for cap in range(p[0], cmax + 1):
opt[0][cap] = v[0]
sel[0][cap] = True
# --- induction case
for i in range(1, n):
for cap in range(cmax + 1):
if cap >= p[i] and opt[i-1][cap - p[i]] + v[i] > opt[i-1][cap]:
opt[i][cap] = opt[i-1][cap - p[i]] + v[i]
sel[i][cap] = True
else:
opt[i][cap] = opt[i-1][cap]
sel[i][cap] = False
# --- reading solution
cap = cmax
solution = []
for i in range(n-1, -1, -1):
if sel[i][cap]:
solution.append(i)
cap -= p[i]
return (opt[n - 1][cmax], solution)
# snip}
[docs]
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 c >= p[0] 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