0-1背包问题的Python算法

前言：

今天上了六节的满课，没有学二进制的东西，就写一下我今天算法分析实验课上对0-1背包问题的解法吧。现在越来越不想上课了，真心觉得现在的课程对我来说是真的没有太大的用途，哎，也不知道该怎么办了。

概述：

其实对于这个0-1背包问题，自我感觉根本的解决办法就是自低向上一步一步得到分析结果，但是分析的话得自顶向下的方向来逐步分析分解问题。

直接贴上代码：

def bag(n,c,w,v) :
	res = [[-1 for j in range(c+1)] for i in range(n+1)]
	for j in range(c+1) :
		res[0][j] = 0
	for i in range(1,n+1) :
		for j in range(1,c+1) :
			res[i][j] = res[i-1][j]
			if j >= w[i-1] and res[i][j]<res[i-1][j-w[i-1]] + v[i-1]:
				res[i][j] = res[i-1][j-w[i-1]] + v[i-1]
	print res
	return res

def show(n,c,w,res) :
	print 'the bigest value is :',res[n][c]
	x = [False for i in range(n)]
	j = c
	for i in range(n,0,-1) :
		if res[i][j]>res[i-1][j] :
			x[i-1] = True
			j -= w[i-1]
	print 'the things we choose are :'
	for i in range(n) :
		if x[i] :
			print 'is the',i
	print ' '

if __name__ = '__main__' :
	n = 5
	c = 10
	w = [2,3,8,5,5]
	v = [10,34,54,12,64]
	res = bag(n,c,w,v)
	show(n,c,w,res)

铁三的比赛马上就要开始了，还有省赛、国赛，还有一大堆社团的事情等着我处理，好烦。看了一下别的赛区的铁三个人赛的题，基本上都是堆溢出相关，目前还没有发现栈溢出和格式化字符串的题，得抓把劲了，目标是进决赛！