理解动态规划先从：

通过金矿模型介绍动态规划

之后，可以通过下面博客的表来理解：

动态规划之01背包问题（最易理解的讲解）

程序实现时，思路和画表时相同

给出程序：http://blog.csdn.net/littlethunder/article/details/26575417

01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),  f[i-1,j] }

# -*- coding: utf-8 -*-
# n为物品数量
# c为背包重量
# w为每个物品重量
# v为每个物品价值
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]
	return res


def show(n, c, w, res):
	print('最大价值为:',res[n][c])
	x = [False for i in range(n)]
	j = c
	for i in range(1,n+1):
		if res[i][j] > res[i-1][j]:
			x[i-1] = True
			j -= w[i-1]
	print('选择的物品为:')
	for i in range(n):
		if x[i]:
			print('第',i,'个,',end='')
	print('')

if __name__ == '__main__':
	n = 4
	c = 10
	w = [5,2,8,3]
	v = [7,3,10,4]
	res = bag(n,c,w,v)
	show(n,c,w,res)

 

 

 

 

 

给出程序