C#用递归算法解决经典背包问题

综合上面的分析，我们可以得到这样的一个处理流程

1）首先建立一个nx(cap+1)的二围数组

2）第一行从尝试选择第一个物品开始

3）对于以后的行，对于每个容量1<=cap<=capacity，首先拷贝上一行同一位置的值下来，如果itemi.Size<=cap并且上一行(cap-itemi.Size)位置上的值与itemi.Value的 和(tempMax)大于拷贝下来的值的话，就将拷贝下来的值替换为上一行(cap-itemi.Size)位置上的值与itemi.Value的 和（tempMax）

4）得到完整数组之后，我们既可以根据数组来确定最优集合了，首先从最后一样最后位置开始，和上一行的同一位置进行比较，如果相同，则该行对应索引的物品不能放到背包中，否则放到背包，并且开始比较上一行与 上上一行在当前背包剩余空间索引出的值，如不等，则对应物品可放置，如此，直到处理到第二行和第一行的比对完成，然后根据当前背包剩余容量与第一个物品的大小比对来确定物品一是否能放置到背包中

4.源程序
 

5.结论

　　上文采用的是动态编程的方法来处理此类背包问题，上面的文章中兄弟们也提到了用递归算法时间复杂度的问题，认为递归算法效率比较低下，这种疑问无可厚非，但递归算法也有它的优点，很多问题都能用递归来解决，我目前学习的就是用这种算法来解决一些常见问题，对于其他算法，比如此问题也可以采用贪婪算法，遗传算法等得以更好的解决，但本文暂不作讨论，以后有时间，一定将这些算法加以实现并详细比较其优劣。