python基于递归解决背包问题详解

递归是个好东西，任何具有递归性质的问题通过函数递归调用会变得很简单。一个很复杂的问题，几行代码就能搞定。   最简单的递归问题：现有重量为weight的包，有若干重量分别为W1,W2…..Wn的物品，试问能否从物品中选出若干件而且重量刚好为weight?   weight具体是怎么构成的，有下面两种情况（假设挑选到Wn时，刚好够weight)：   1. 从Wn-1开始就已经够weight，那weight=W1+W2+……+Wn=W1+W2+……+Wn-1.   2.加上Wn后刚好够weight,那自然地有weight=W1+W2+……+Wn.   上面两种情况一个有解，那问题就有解，于是我们