首先，先请大家了解一下动态规划以及背包问题是啥，已经了解的请略过 动态规划 动态规划与分治法相似，都是通过组合子问题的解来求解原问题，它通常用来求解最优化问题，这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最大值或者最小值）的解。我们称这样的解为问题的一个最优解，而不是最优解，因为可能有多个解都达到最优**值。 背包问题 给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 解决方法 我们首先介绍思路，再通过代码进行解释。 遇到这种问题，最简单也是最耗费时间的解决方法是遍历，将所有情况都计算出来，再从结果中找最优解，我们今天介绍的动态规划就是在这个基础上演变而来的。 我们都知道，遍历之所以耗费时间，是由于它的计算量巨大，我们通过观察它的计算过程可以发现，其实它的很多计算操作计算的都是之前计算过的量。那我们如果把这些已经计算过的量储存起来，当我们需要的适合直接提取它的结果，就起到了减少计算量的效果，我们的动态规划使用的就是这种思想。 读到这里，大家可能有一种似懂非懂的感觉，下面我们直接贴上代码为大家解释一下。
#-*- coding: utf-8 -*- def max(m,n): if(m>n): return m if(m<n): return n def max1(m,n): if(m<n): return true if(m>n): return false def best(m,list1,list2,n): r=[[0 for i in range(n)] for i in range(m+1)]; for i in range(m+1): for j in range(n): r[i][j]=0 for i in range(1,m+1): for j in range(1,n): r[i][j] = r[i][j-1] if(i>=list1[j]): r[i][j]=max(r[i][j-1],r[i-list1[j]][j-1]+list2[j]) return r[m][n-1]; if __name__ =="__main__": m= 0; print"请输入最大重量" m = input() print"请输入一组物品的总数量" n=input() n=n+1 list1 = [0 for i in range(n)] list2 = [0 for i in range(n)] print"请依次输入物品的质量" for i in range(1, n): list1[i] = int(input()) print"请依次输入物品的价值" for i in range(1, n): list2[i] = int(input()) list3[i]=0 q=best(m,list1,list2,n) print q 这段代码最重要的部分就是best函数，我们来一行一行分析一下。 首先它创建了一个m+1行n列的数组，用于存储我们已经计算过的数据，r[m][n-1]的意思就是当背包最大重量为m、物品为前n个时，能装下的物品总价格最高的值。（要注意到我们在主函数输入n之后将n加1一次，这么做是为了方便计算，把n加1后可以留出来n=0的位置表示没有物品时的最优解的值） 接下来我们把r数组初始化为0,然后，运用动态规划的基本思想，先限制一个背包的最大重量，再挨个的增加物品数量，求它的最大值，为了理解方便，我们通过这个图来解释。我们现在有五个物品abcde，weight是他们的重量，value是他们的价格，浅蓝色的是我们限制的最大重量。那么这张图是怎么得来的呢？ 以当最大重量为6时，a行的12的计算方法为例。这就关系到我们代码中最关键的一行： r[i][j]=max(r[i][j-1],r[i-list1[j]][j-1]+list2[j]) 其中r[i][j]是我们要计算的结果，我们要通过比较r[i][j-1]与r[i-list1[j]][j-1]+list2[j]的值来判断是否把a放进去，此时i=6，j=5（这个图是从下往上生成的，与我们的代码循环方式相反）r[i][j-1]的值可以从表上得到为9，,r[i-list1[j]][j-1]+list2[j]的意思为把a所占的重量出去后bcde在总重量减去a重量的限制中能达到的最优解，减去a后总重量为4，我们可以在b那一行，浅蓝色栏为4的表格中找到此时最优解为6，之后再加上a的价格，就得出了12，再最后与9比较，12大于9，所以12就是我们要的最优解。整个算法就是这样一步一步计算过来的。
