Knapsack

gistfile1.py

#!/usr/bin/python3


data = [(2,3), (4,7), (1,1), (3,8)]
q_max = 8

# wrong: p = [[0] * (q_max+1)] * (len(data) + 1)
p = [[0 for j in range(q_max+1)] for i in range(len(data)+1)]
ps = [[None for j in range(q_max+1)] for i in range(len(data)+1)]

for i in range(len(data)):
    for q in range(0, q_max+1):
        if i == 0:
            if q <= data[i][0]:
                p[i][q] = 0
                ps[i][q] = set()
            else:
                p[i][q] = data[i][1]
                ps[i][q] = set([i])
        else:
            if q < data[i][0]:
                p[i][q] = p[i-1][q]
                ps[i][q] = ps[i-1][q].copy()
            else:
                a = p[i-1][q]
                b = p[i-1][q - data[i][0]] + data[i][1]
                if a > b:
                    p[i][q] = a
                    ps[i][q] = ps[i-1][q].copy()
                else:
                    p[i][q] = b
                    ps[i][q] = ps[i-1][q - data[i][0]].copy()
                    ps[i][q].add(i)
    print(p[i])
    print(ps[i])