01背包问题：1.递归思想0- 1 背包问题如果采用递归算法来描述则非常清楚明白, 它的算法根本思想是假设用布尔函数knap( s, n) 表示n 件物品放入可容质量为s 的背包中是否有解( 当knap 函数的值为真时说明问题有解,其值为假时无解) . 我们可以通过输入s 和n 的值, 根据它们的值可分为以下几种情况讨论:( 1) 当s= 0时可知问题有解, 即函数knap( s, n) 的值为true; ( 2) 当s< 0 时这时不可能,所以函数值为false; ( 3) 当输入的s> 0 且n< 1 时即总物品的件数不足1, 这时函数值为false,只有s> 0 且n \1 时才符合实际情况,这时又分为两种情况: ( 1) 选择的一组物体中不包括Wn则knap( s, n) 的解就是knap( s, n- 1) 的解. ( 2) 选择的一组物体中包括Wn 则knap( s, n) 的解就是knap( s- Wn, n- 1) 的解. 这样一组Wn 的值就是问题的最佳解. 这样就将规模为n 的问题转化为规模为n- 1 的问题. 综上所述0- 1 背包问题的递归函数定义为:knap( s, n) =∕true, s= 0             ︳false, s< 0             ︳false, s> 0 且n< 1              \knap( s, n- 1) 或knap( s- Wn, n- 1) , s> 0 且n>= 1采用此法求解0- 1 背包问题的时间复杂度为O( n) . 上述算法对于所有物品中的某几件恰能装满背包时能准确求出最佳解. 但一般情况是对于某一些物品无论怎么装都不能装满背包, 必须要按背包的最大容量来装. 如物品件数为4, 其质量分别为: 10, 2, 5, 4, 背包的容量为20, 则这四件物品无论怎么放都不能恰好装满背包, 但应能最大限度装, 即必须装下10, 5, 4 这三件物品, 这样就能得到最大质量19. 对于这种装不满的背包它的解决办法是这样的: 按所有物品的组合质量最大的方法装背包, 如果还装不满,则我们可以考虑剩余空间能否装下所有物品中最小的那件, 如果连最小的都装不下了则说明这样得到的解是最佳解, 问题解决. 这样我们必须先找出所有n 件物品中质量最小的那件( 它的质量为Min) , 但是为了问题的解决我们不能增加运算次数太多, 并且必须运用上述递归函数. 那么我们可通过修改s 的值即背包的容量, 从背包容量s 中减去k( 它的值是从0 到Min- 1 之间的一个整数值) , 再调用递归函数. 当k= 0 时即能装满背包, 其它值也能保证背包能最大限度装满, 这样所有问题都解决了.Description 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。 问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。 如果有满足条件的选择，则此背包有解，否则此背包问题无解。  Input输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）多组测试数据。 Output对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO“ Sample Input20 51 3 5 7 9Sample OutputYES复制代码# include<stdio.h># include<string.h>int date[1005];int f(int w,int s){    if(w==0) return 1;//正好    if(w<0||w>0 &&s==0) return 0;    if(f(w-date[s],s-1)) return 1;//退出来再选下一个     return f(w,s-1);//选择下一个}int main(){ int i,Weight,n; while(scanf("%d %d",&Weight,&n)!=EOF) {     memset(date,0,sizeof(date)); for(i=1;i<=n;i++)  scanf("%d",&date[i]);    if(f(Weight,n))       printf("YES\n"); else printf("NO\n"); } return 0;}}http://i.cnblogs.com/EditPosts.aspx?opt=1