Skip to content

Instantly share code, notes, and snippets.

@takaki
Last active Dec 15, 2015
Embed
What would you like to do?
Knapsack
#!/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])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment