# Knapsack-problem
背包问题，使用递归和动态规划两种思路并比较运行速度，python语言。
其主要思想如下：
背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。
对编号为a,b,c,d,e的五件物品，重量分别是2,2,6,5,4，价值分别是6,3,5,4,6，背包承重为10，计算如下表：
n w v 1 2 3 4 5 6 7 8 9 10
a 2 6 0 6 6 9 9 12 12 15 15 15
b 2 3 0 3 3 6 6 9 9 9 10 11
c 6 5 0 0 0 6 6 6 6 6 10 11
d 5 4 0 0 0 6 6 6 6 6 10 10
e 4 6 0 0 0 6 6 6 6 6 6 6
这张表是至底向上，从左到右生成的（d4单元格，表示只有物品e，d时,承重为4的背包所能装入的最大价值）。
