爱华网问题：给定一个载重量为m的背包，以及n个重量为wi、价值为pi的物体，1<=i<=n，要求把物体装入背包，使背包内的物体价值最大，把这类问题称为背包问题。通常称物体不可分割的背包问题为0/1背包问题。
这个问题也可以用动态规划的分阶段决策方法，来确定把哪一个物体装入背包的最优决策。类似于资源分配那样，令optp[i][j]表示在前i个物体中，能够装入载重量为j的背包中的物体的最大价值，j=1,2,…,m。可以得到下面的动态规划函数：
optp[i][0]=optp[0][j]=0………………………………………..(1)
optp[i][j]=optp[i-1][j](j<wi)…………………………………(2)
optp[i][j]=max{optp[i-1][j],optp[I-1][j-wi]+pi}(j>=wi)…(3)
式(1)表示，把前面i物体装入载重量为0的背包，或者把0个物体装入载重量为j的背包，得到的价值都为0。（2）式表明，如果第i个物体的重量大于背包的载重量，则装入前面i个物体得到的最大价值，与装入前面i–1个物体得到的最大价值一样（第i个物体没有装入背包）。式（3）表明，当第i个物体的重量小于背包的载重量时，如果把第i个物体装入载重量为j的背包后总价值上升，那么就装入，否则不装入。
算法实现如下（Python编写，经测试可用）：
#!/usr/bin/python
#-*-coding:utf8-*-
'''
Createdon2011-10-24
@author:AHAN
python2.7.2
'''
#n个物体的重量(w[0]无用)
w=[0,2,2,6,5,4]
#n个物体的价值(p[0]无用)
p=[0,6,3,5,4,6]
#计算n的个数
n=len(w)-1
#背包的载重量
m=10
#装入背包的物体，元素为True时，对应物体被装入(x[0]无用)
x=[Falseforrawinrange(n+1)]
v=0
#optp[i][j]表示在前i个物体中，能够装入载重量为j的背包中的物体的最大价值
optp=[[0forcolinrange(m+1)]forrawinrange(n+1)]
defknapsack_dynamic(w,p,n,m,x):
#计算optp[i][j]
foriinrange(1,n+1):
forjinrange(1,m+1):
optp[i][j]=optp[i-1][j]
if(j>=w[i])and(optp[i-1][j-w[i]]+p[i]>optp[i-1][j]):
optp[i][j]=optp[i-1][j-w[i]]+p[i]
#递推装入背包的物体
j=m
foriinrange(n,0,-1):
ifoptp[i][j]>optp[i-1][j]:
x[i]=True
j=j-w[i]
#返回最大价值
v=optp[n][m]
returnv
print('最大值为：'+str(knapsack_dynamic(w,p,n,m,x)))
print(x[1:])
