Algorithms/knapsack.py at master · streethacker/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/python
#-*- coding:utf-8 -*-

def Knapsack(v, w, c, n, m):
	jMax = min(w[n]-1, c)
	for j in range(jMax+1):	m[n][j] = 0
	for j in range(w[n], c+1):	m[n][j] = v[n]

	for i in range(n-1, 1, -1):
			jMax = min(w[i]-1, c)
			for j in range(jMax+1):	m[i][j] = m[i+1][j]
			for j in range(w[i], c+1):	m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i])

	m[1][c] = m[2][c]

	if c>=w[1]:
			m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1])

def TraceBack(m, w, c, n, x):
	for i in range(1, n):
			if m[i][c] == m[i+1][c]:
					x[i] = 0
			else:
					x[i] = 1
					c -= w[i]
	x[n] = 1 if m[n][c] else 0

if __name__ == "__main__":
		n, c = 5, 10
		w = [0, 2, 2, 6, 5, 4]
		v = [0, 6, 3, 5, 4, 6]

		m = [[0 for i in range(c+1)] for j in range(n+1)]

		x = [0 for i in range(n+1)]

		Knapsack(v, w, c, n, m)

		TraceBack(m, w, c, n, x)

		weight, value = 0, 0
		print "Result Vector:",
		for i in range(1, len(x)):
				if x[i] == 1:
						weight += w[i]
						value += v[i]
				print x[i],

		print

		print "Total Weight:%s" % weight
		print "Total Value:%s" % value